Application Center - Maplesoft
  Submit your work
Application Center Applications Chinese Remainder Theorem Preview

App Preview:

Chinese Remainder Theorem

You can switch back to the summary page by clicking here.

Learn about Maple
Download Application



 

                                 CHINESE REMAINDER  THEOREM

                                          Author  Roland Engdahl
                                            mr.engdahl@telia.com

 

INTRODUCTION
 

 

 

Literature
Kumanduri and Romero,  Number theory with computer application

Knuth,  Seminumerical Algorthms, The Art of Computer Programming

Cohn,  Advanced Number Theory

Let r[i] (remainders) and m[i] (moduli)  be integers

Study a system of n simultaneous congruences

        x ≡ r[i] mod m[i]    i = 1...n

Given are the values of r[i] and m[i]
 
Chinese Remainder Theorem
Let


A constructive PROOF at the the MAIN PROGRAM below

Generalizaton of the theorem above (without pairwise relatively prime)
...The system of congruences
   x ≡
   has a solution if and only if
   for all   i ≠ j  GCD(

     

 For given r[i] and m[i]  i= 1 ... n  we wish to determine x (if it exists)


    DESIGN

1.  Is there is a solution to the system?

      Y   there is     go  to 2 ...

      N   otherwise break

2.  There is a solution  

       are the moduli  pairwise relative prime?

       Y go to  3 Main Program

       N otherwise factorize the moduli and make a new list of  then go to 3

3. Solve with Main Program

IS THERE A SOLUTION TO THE GIVEN SYSTEM?
 

 

The system has a solution if and only if

for all i ≠ k GCD(m[i],m[k]) is a divisor to abs(r[i]-r[k])   

 

> 

restart:n:=6:so:=true:
m[1]:=473:r[1]:=322:
m[2]:=517:r[2]:=476:
m[3]:=611:r[3]:=241:
m[4]:=637:r[4]:=163:
m[5]:=651:r[5]:=100:
m[6]:=657:r[6]:=565:

for i from 1 to n-1 do
  for k from (i+1) to n do
  if (abs(r[i]-r[k]) mod gcd(m[i],m[k]))<>0 then so:=false end if;
end end;
if so then "there is a solution"
 else "there is NO solution" end if;

for i from 1 to n do mc[i]:=m[i] end do:nc:=n:   This line pc[i] to keep m[i]  for control after calculatiom 

(2.1)

If there is no solution BREAK else CONTINUE

TESTING   IF THE  MODULI  ARE  PARWISE RELATIVELY  PRIME INTEGERS
 

 

> 

relpr:=true:
for i from 1 to n-1 do
  for k from (i+1) to n do
  if gcd(m[i],m[k]) <>1 then relpr:=false end if
end
end:
if relpr then "CONTINUE WITH MAIN PROGRAM"
  else "CONTINUE WITH Factorize" end if;

(3.1)

Factorize the moduli

> 

for i from 1 to n do
  ifactor (m[i])
end do;

 

 

 

 

 

(3.2)

METHOD for transforming the moduli to RELATIVLY PRIME INTEGERS
If a solution exists and the moduli are not relatively prime we can construct a new system where the moduli are relatively prime
by using the follwing simple observation:
Assume   u>0,  v>0  m = u*v
Every congruence class modulo m corresponds to a unique pair of classes, that is,
x ≡ y  (mod m) 0x ≡ y  (mod u) and x ≡ y  (mod v)
GCD(u,v) = 1 0  every pair of congruence classes mod u and mod v corresponds to a single congruence class mod m = u*v
Here we have the factors as primes or a power of primes

The table of results for factorize we designate above    L1, L2 ... L6
Acccording to the lemma
We split up L1 in two parts  11 and 43 and keep the remainder 322.  
We split up L2 in two parts  11 and 47 and keep the remainder 476
We split up L3 in two parts  13 and 47 and keep the remainder 241
In L1 and L2 we have the same prime (11) and they are in the same congruence class so we can exclude one of them, say 11 in L2
In L2 and L3 we have the same prime (47)                                                                                                                      47 in L2
Thus L2 is empty

Preserved in the example Ex A below are  lines m[1],...,m[4]
For prime powers take only the highest power
In L4 we have (7^2) so exlcude (7) in L5
In L6 we have (3^2) so exclude (3) in L5
New table for m[i] in example Ex A in MAIN PROGRAM  below.

MAIN PROGRAM
 

       Ex A

> 

r[1]:=322:m[1]:=11:                 
r[2]:=322:m[2]:=43:
r[3]:=241:m[3]:=13:
r[4]:=241:m[4]:=47:
r[5]:=163:m[5]:=49:
r[6]:=100:m[6]:=31:
r[7]:=565:m[7]:=9:
r[8]:=565:m[8]:=73:
n:=8:

 

 (4.1)

 

> 

r[1]:=322:m[1]:=11*43:
r[2]:=241:m[2]:=47*13:
r[3]:=163:m[3]:=49:
r[4]:=100:m[4]:=31:
r[5]:=565:m[5]:=9*73:
n:=5:

 

 (4.2)

 

> 

r[1]:=322:m[1]:=43:                 
r[2]:=476:m[2]:=11:
r[3]:=241:m[3]:=47*13:
r[4]:=163:m[4]:=49:
r[5]:=100:m[5]:=31:
r[6]:=565:m[6]:=9*73:
n:=6:

 

> 

inver:=proc(x::integer,y::integer)::integer;
  local te,t,s,d,q,r; global u,a,b;
  te:=y: s:=1:t:=0:a:=x;b:=y;r:=1:
  while r>0 do
  q:=iquo(a,b):r:=a mod b:
  a:=b:b:=r:d:=s-t*q:
  s:=t:t:=d:
end do;
if s<0 then s:=s+te: end if;
u:=s;
u;
end proc:
                                                                                                                                           

 

> 

Mp:=1:for i from 1 to n do Mp:=Mp*m[i] end do:   
for i from 1 to n do Mq[i]:=iquo(Mp,m[i]) end do:
for i from 1 to n do x[i]:=inver(Mq[i],m[i]) end do:
xp:=0: for i from 1 to n do xp:=xp+ r[i]*Mq[i]*x[i] end do:xp:=xp mod Mp;
                                           

 

 (4.3)

 

 


PROOF  of Chinese Remainder Theorem
Quotation from Kumanduri and Romero  (notation changed a little to fit a Maple  program)
A   Let Mp =
B   Let = Mp /
Since the pairwise relatively prime, Mq[i]is relatively prime to  m[i]
C    so it has an inverse x[i] modulo m[i]             that
If i ≠ k then
D   Then                
                xp = r[1] Mq[1] x[1] + r[2] Mq[2] x[2] + ... +  r[n] Mq[n] x[n]      mod Mp

The solution is unique mod Mp     (The proof is easy)

 

CONTROL  OF RESULT from original values
 

 

> 

for i from 1 to nc do
  rc[i]:=xp mod mc[i] end do;

 

 

 

 

 

(5.1)

EXERCISE
 
> 

m[1]:= 23916497:
m[2]:= 31663333:
m[3]:= 43817891:
m[4]:= 43716739:
> 

r[1]:= 16967183:
r[2]:= 11431757:                                                               
r[3]:= 42314739:
r[4]:= 36345245:

In the result the first seven digits is the N latitude and the last eight digits the E longitude

The format is     N    X

′.yyy

With luck you will find my coordinates (mr.engdahl@telia.com         choose subject as Chinese cache)
> 

Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author

are responsible for any errors contained within and are not liable for any damages resulting from the use of this material.

This application is intended for non-commercial, non-profit use only.

Contact the author for permission if you wish to use this application in for-profit activities.