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=: p: 5 ?. 100x
211 541 89 307 191
] r=: b|5 ?.@\$ 10^6x
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 RogerHui.

Essays/Chinese Remainder Theorem (last edited 2008-12-08 10:45:35 by anonymous)