Essays/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 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 specifies 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 relatively prime, then such an integer c always exists.

g0    =: , ,. =@i.@2:
it    =: {: ,: {. - {: * <.@%&{./
gcd   =: (}.@{.) @ (it^:(*@{.@{:)^:_) @ g0

assert=: 3 : 'assert. y'
ab    =: |.@(gcd/ * [ % +./)@(,&{.)
cr1   =: [: |/\ *.&{. , ,&{: +/ .* ab
chkc  =: [: assert ,&{: -: ,&{. | {:@cr1
cr    =: cr1 [ chkc

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

   4 gcd 6                  NB. GCD as a linear combination
_1 1

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

   4|9                      NB. verify residue 0
1
   6|9                      NB. verify residue 1
3

   4 1 cr 6 0               NB. remainder may not exist if bases are not relatively prime
|assertion failure: assert
|   y

If b is a list of bases and r the corresponding residues, c=:cr/b,.r computes the remainder c such that r=b|c .

   b=: 211 541 89 307 191
   r=: 112 165 7 80 70

   ] 'x c'=: cr/ b,.r
595719024643 240834386890

   b|c
112 165 7 80 70
   r
112 165 7 80 70

   *./ b
595719024643
   x
595719024643

---

Contributed by Roger Hui.