Differences between revisions 9 and 10
 ⇤ ← Revision 9 as of 2007-09-05 21:26:44 → Size: 1851 Editor: RogerHui Comment: ← Revision 10 as of 2008-12-08 10:45:35 → ⇥ Size: 1852 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 6: Line 6: The [:../Euclidean Algorithm:Euclidean algorithm] computes the GCD The [[../Euclidean Algorithm|Euclidean algorithm]] computes the GCD Line 72: Line 72: [[BR]] <
>

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)