Essays/Chinese Remainder Theorem
< Essays
Jump to navigation
Jump to search
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.