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:

#include "gcd.bas"
function mul_inv( a as integer, b as integer ) as integer
	if b = 1 then return 1
    for i as integer = 1 to b
        if a*i mod b = 1 then return i
    next i
    return 0
end function
 
function chinese_remainder(n() as integer, a() as integer) as integer
	dim as integer p, i, prod = 1, sum = 0, ln = ubound(n)
	for p = 0 to ln-1
	    for i = p+1 to ln
	        if gcd(n(i), n(p))>1 then 
	            print "N not coprime"
	            end
	        end if
	    next i
	next p
	for i = 0 to ln
	    prod *= n(i)
	next i
	for i = 0 to ln
	    p = prod/n(i)
	    sum += a(i) * mul_inv(p, n(i))*p
	next i
	return sum mod prod
end function
 
dim as integer n(0 to 2) = { 3, 5, 7 }
dim as integer a(0 to 2) = { 2, 3, 2 }
 
print chinese_remainder(n(), a())