Chinese Remainder Theorem

The  Chinese Remainder Theorem is  a method to solve simultaneous    congruences. There is a formula for the solutions to simultaneous congruences, but it is simpler to solve them 2 at a time.  Suppose we have two congruences
 
  x = a  (mod m) and  x =b (mod n),
  
 where (m, n)=1. To solve this we can express  1 as a linear combination of m and n using the Extended Euclidean algorithm.
   
    Write  u m + v n =1. Then  a solution to the simultaneous congruence is
    
     x0= um  b + vn  a.  Since  vn   is congruent to 1 modulo m, we have x0 = a (mod m). Similarly x0=  b (mod n). 
     
      The linear combination of u and v is found by the ExtendedGCD  function.  For example, consider 
      
       x= 3 (mod 11)
       x= 7 (mod 18).
      First compute the ExtendedGCD of 11 and 18.

ExtendedGCD[11,18]

The result is  a list with two elements.  The first element is the GCD and the second  value gives the u and v such that 11 u + 18 v = GCD[11,18]=1. In this case,  11 (5) + 18 (-3) =1. Therefore the solution to our congruence is 
 x= 11 (5) 7 + 18 (-3) 3. Lets verify that this satisfies the congruences.

x= 11 5 7 + 18 (-3) 3

Mod[x, 11]
Mod[x, 18]

This technique can be used to solve more than two simultaneous congruences. We solve them two at a time. Suppose we have the  following simulataneous congruences:
      
      x= a1 (mod m1),
      x= a2 (mod m2),
      
      x=ak (mod mk),
      
       where the moduli mi are pairwise  relatively prime. Then we solve the first two by   the technique outlined above to get a  solution x0 (mod m1m2). Now we have  k-1 congruences:
       
        x= x0 (mod m1m2)
        x= a3  (mod m3)
        
        x= ak (mod mk)
       
       Here is the program which solves the simultaneous congruence. It takes two arguments, a list  of values of ai and a corresponding list of values of mi.

crt[a_List, m_List]:= Module[ {i,x,n,k },
      (*initialize*)   i=1; x= a[[1]]; n=m[[1]];
   
      If[ Length[a]== Length[m],
       (*then*)k=Length[a];
           While[ i<k,
                 i++;
                 {u,v}= ExtendedGCD[m[[i]], n][[2]];
                 x=u m[[i]] x + v n a[[i]] ;
                 n=m[[i]] n;
                 x=Mod[x,n]];
           Return[x],
      (*else*) Return["Both lists have to be the same length"]]]

Examples:

The congruence  x= 1(mod 2) and x= 2 (mod 3) is  solved by the  following command. The smallest positive solution is 5.

crt[ {1, 2}, {2,3}]

The list of ai's and the moduli mi's have to be the same
 length, otherwise the problem is incorrectly posed.

crt[{1,2,1}, {3,2}]

crt[{3,5,6}, {11, 7, 10}]

crt[{6,5}, {8, 13}]

crt[{1,4,2}, {2,5,9}]

Exercise: Modify the program to  return more than one solution. Recall that if the moduli are pairwise relatively prime, then  the  solutions differ by multiples of the product of the moduli mi.

Exercise: Modify the program to solve congruences when the moduli are not pairwise relatively prime.