Problem Statement

Suppose

n

1

{\displaystyle n_{1}}

,

n

2

{\displaystyle n_{2}}

,

…

{\displaystyle \ldots }

,

n

k

{\displaystyle n_{k}}

are positive integers that are pairwise co-prime.   Then, for any given sequence of integers

a

1

{\displaystyle a_{1}}

,

a

2

{\displaystyle a_{2}}

,

…

{\displaystyle \dots }

,

a

k

{\displaystyle a_{k}}

,   there exists an integer

x

{\displaystyle x}

solving the following system of simultaneous congruences: Furthermore, all solutions

x

{\displaystyle x}

of this system are congruent modulo the product,

N

n

1

n

2

…

n

k

{\displaystyle N=n_{1}n_{2}\ldots n_{k}}

.

Write a program to solve a system of linear congruences by applying the   Chinese Remainder Theorem. If the system of equations cannot be solved, your program must somehow indicate this. (It may throw an exception or return a special false value.) Since there are infinitely many solutions, the program should return the unique solution

s

{\displaystyle s}

where

0 ≤ s ≤

n

1

n

2

…

n

k

{\displaystyle 0\leq s\leq n_{1}n_{2}\ldots n_{k}}

.

Show the functionality of this program by printing the result such that the

n

{\displaystyle n}

's   are

[ 3 , 5 , 7 ]

{\displaystyle [3,5,7]}

and the

a

{\displaystyle a}

's   are

[ 2 , 3 , 2 ]

{\displaystyle [2,3,2]}

.

Algorithm:   The following algorithm only applies if the

n

i

{\displaystyle n_{i}}

's   are pairwise co-prime. Suppose, as above, that a solution is required for the system of congruences: Again, to begin, the product

N

n

1

n

2

…

n

k

{\displaystyle N=n_{1}n_{2}\ldots n_{k}}

is defined. Then a solution

x

{\displaystyle x}

can be found as follows: For each

i

{\displaystyle i}

,   the integers

n

i

{\displaystyle n_{i}}

and

N

/

n

i

{\displaystyle N/n_{i}}

are co-prime. Using the   Extended Euclidean algorithm,   we can find integers

r

i

{\displaystyle r_{i}}

and

s

i

{\displaystyle s_{i}}

such that

r

i

n

i

s

i

N

/

n

i

= 1

{\displaystyle r_{i}n_{i}+s_{i}N/n_{i}=1}

. Then, one solution to the system of simultaneous congruences is: and the minimal solution,

Let's start with the solution:

import scala.util.{Success, Try}

object ChineseRemainderTheorem extends App {

  def chineseRemainder(n: List[Int], a: List[Int]): Option[Int] = {
    require(n.size == a.size)
    val prod = n.product

    def iter(n: List[Int], a: List[Int], sm: Int): Int = {
      def mulInv(a: Int, b: Int): Int = {
        def loop(a: Int, b: Int, x0: Int, x1: Int): Int = {
          if (a > 1) loop(b, a % b, x1 - (a / b) * x0, x0) else x1
        }

        if (b == 1) 1
        else {
          val x1 = loop(a, b, 0, 1)
          if (x1 < 0) x1 + b else x1
        }
      }

      if (n.nonEmpty) {
        val p = prod / n.head

        iter(n.tail, a.tail, sm + a.head * mulInv(p, n.head) * p)
      } else sm
    }

    Try {
      iter(n, a, 0) % prod
    } match {
      case Success(v) => Some(v)
      case _          => None
    }
  }

  println(chineseRemainder(List(3, 5, 7), List(2, 3, 2)))
  println(chineseRemainder(List(11, 12, 13), List(10, 4, 12)))
  println(chineseRemainder(List(11, 22, 19), List(10, 4, 9)))

}