44. Chinese Remainder Theorem

Given: integer pairs (m,r) and (n,s) where m and n are bases and r and s are residues with respect to the bases. The extended Euclidean algorithm computes the GCD of m and n as a linear combination; that is, finds integers a and b such that (m∨n) = (a×m)+(b×n) . The Chinese Remainder Theorem asserts that

   c← (m∧n) | (m∨n) ÷⍨ (r×b×n)+(s×a×m)

satisfies r=m|c and s=n|c . If m and n are co-prime, then such an integer c always exists.

assert←{⍺←'assertion failure' ⋄ 0∊⍵:⍺ ⎕signal 8 ⋄ shy←0}

xea←{(⍺,1 0) {0=⊃⍵:⍺ ⋄ ⍵ ∇ ⍺-⍵×⌊(⊃⍺)÷⊃⍵} (⍵,0 1)}       

cr←{
  m r←⍺
  n s←⍵
  gcd a b←m xea n
  lcm←m×n÷gcd
  c←lcm|gcd÷⍨(r×b×n)+(s×a×m)
  assert(r=m|c)∧(s=n|c):
  lcm,c
}

xea is the extended Euclidean algorithm; the anonymous function contained therein is the ordinary Euclidean algorithm. For m xea n , arguments to the anonymous function are triplets, the numbers p and q whose GCD is to be found augmented with with coefficients, (p,pm,pn) and (q,qm,qn) , such that p=(pm×m)+(pn×n) and q=(qm×m)+(qn×n) . Arithmetic steps of the Euclidean algorithm are applied to the arguments and to the coefficients, producing a triplet result.

cr applies to two (base,residue) pairs and produces (LCM,remainder) of the LCM of the bases and the required remainder.

   4 xea 6       ⍝ GCD as a linear combination
2 ¯1 1

   4 1 cr 6 3    ⍝ applies to (base,residue) pairs
12 9             ⍝ produces (LCM, remainder)

   4|9           ⍝ verify residue 0
1
   6|9           ⍝ verify residue 1
3

   4 1 cr 6 0    ⍝ may not exist if bases are not co-prime
assertion failure
cr[9] assert(r=m|c)∧(s=n|c):
     ∧

   b← 12 5 11 7 23 19 29
   r←  2 2 10 3 13  8  8

   ⊢ x c ← ⊃ cr/ ↓b,⍪r
58549260 26014922

   b|c
2 2 10 3 13 8 8
   r
2 2 10 3 13 8 8
       
   ∧/b
58549260
   x
58549260

Because of the limited precision of IEEE 64-bit floating point numbers cr can fail even on moderately large arguments, but the algorithm is valid on extended precision numbers. In J:

   b
1187 491 6203 4973 7331 251 7417 937 5557
   r
301 480 2120 4692 7251 61 6522 52 4003

   x,c  ⍝ the results produced by cr
1277608107627134918695982763739 1175902400063622064889011467782

   b|c
301 480 2120 4692 7251 61 6522 52 4003
   r
301 480 2120 4692 7251 61 6522 52 4003

Appeared in J in [121, 122].