Chinese Remainder Theorem for Integers

This programme verifies the Chinese Remainder Theorem for Integers (of "congruence").

This programme verifies the Chinese Remainder Theorem for Integers (of "congruence").

Assume that we are to find a solution c_soln such that :
c_soln =eqvt mod (4, 7)
c_soln =eqvt mod (5, 17)
c_soln =eqvt mod (6, 23)
c_soln =eqvt mod (7, 47)
where "=eqvt" implies "congruence" with the usual symbol of 3 equal-to lines.

The solution is c_soln = 124275
It can be verified by for eg : mod (124275, 7) = 4 ; mod (124275, 17) = 5 ;

Now, how did we find this c_soln ?
The answer is the Chinese Remainder Theorem for Integers - refer NK/P21 :
Suppose that we need to solve a system of congruences to DIFFERENT moduli :
c_soln =eqvt mod (c1, m1)
c_soln =eqvt mod (c2, m2)
...
c_soln =eqvt mod (ck-1, mk-1)

Given a set of coprimes mk and a corresponding set of residues ck,
the unique non-negative solution c_soln < M that will satisfy
(c_soln < M because of mod M below)
c_soln =eqvt mod (ck, mk) for k = 1, 2, ... K is given by :
c_soln = mod ( sum ( (ck .* Nk) .* Mk ), M )
where Nk satisfies :
Gk = [ 1, 1, 1 ... 1 ] = Nk.*Mk + nk.*mk
and M = prod (mk)

Refer Chinese Remainder Theorem in the books by :
Richard Blahut (RB) / P70 and Neal Koblitz (NK) / P21

Extending further, I have used the above c_soln to solve problems when
the LHS has coeffs of x other than 1. For eg, refer Problem NK / 11c in P25.
Let us call it the "Extended Chinese Remainder Theorem for Integers".

In this programme, in addition to the solution wrt the input ck values, we
also check this theorem wrt values ck_check = mod (c, mk) with c = 1 : M-1
If we encounter a singular "black hole" point where the theorem
"apparently" fails, we publish those values for further investigation.
This is achieved by setting str_Only_Soln to 'N'. Default option is 'Y'.

Refs to my other related Programmes, Ref books and a suitable Matlab Dir :
--------------------------------------------------------------------------
Poly_GCD : Old Name : Poly_GCD_Top.m
Simple programme : Poly_ADD_SUB.m to add or subtract polys.
Simple programme : Poly_DEG for getting the degree of a Polynomial
A Complex Programme : Poly_POWER for P = poly^pow
A Complex Programme : CMPLX_GCD for finding GCD of Complex Numbers
Gaussian Integers' Programme : Gen_Primes_Eq_2_Sqs.m which generates
prime numbers which are sum of squares of two integers.
A Medium Complexity Programme :
Ch_Rem_Thr_Int for finding Congruency Solution of Numbers using
the Chinese Remainder Theorem
A Complex Programme :
Ch_Rem_Thr_Poly for finding Congruency Solution of Polynomials using
the Chinese Remainder Theorem
A Medium Complexity Programme :
Diophantine_1.m to generate Diophantine Equation Numbers

I think that all these functions : Poly_GCD, Poly_POWER, CMPLX_GCD,
Ch_Rem_Thr_Poly.m, Ch_Rem_Thr_Int.m, Gen_Primes_Eq_2_Sqs etc are essential as commonly required functions,
and can be placed in the dir : ...\matlab\specfun