ABSTRACT
The premise is a pair of linear congruences having the same modulus r. Let a1,a2; b1,b2; c1,c2 be integers. One considers
a1x1 + a2x2 ≡ c1 (mod r) b1x1 + b2x2 ≡ c2 (mod r).(A)
If D = a1 a2b1 b2
,D1 = c1 b1 c2 b2
,D2 = a1 c1 a2 c2
,one gets
Dx1 ≡ D1 (mod r) Dx2 ≡ D2 (mod r)(B)
If g.c.d (D,r) = 1, the congruences (B) have solution 〈t1, t2〉 where t1, t2 are unique modulo r. These give a solution of the system (A) above. In the same manner, if there are m congruences in m unknowns all taken to the same modulus r, they can be reduced to m independent congruences involving only one unknown as in (B) above. These give a unique solution (mod r). A different context is when we have a system of m congruences in a single unknown but taken to different moduli. This problem was solved by Chinese mathematicians as early as the rst century A.D. The earliest reference is that of Sun Tsu [18]. But, at about the same period Nichomachus (born in Gerasa, Palestine c 100 A.D.) is known to have solved the problem in his “Introductio to Arithemeticae”. An example is:
Find the least positive integer which upon division by 3 leaves a remainder 2, upon division by 5 leaves a remainder 3 and upon division by 7 leaves a remainder 2. In symbols, one has
x≡ 2(mod 3), x≡ 3(mod 5) and x≡ 2(mod 7). A common solution is x≡ 23 (mod 3 ·5 ·7). The gist of the idea is that the solutions to
x≡ bi(mod ri) (i = 1,2, · · · ,k) 105
form a progression with period ri. The Chinese Remainder Theorem says that k arithmetic progressions with pairwise relatively prime moduli have a non-empty intersection. It is just an assertion of the fact that the cosets of the ideals riZ (i = 1,2, · · · ,k) t nicely into a particular coset of the ideal NZ where N = r1r2 · · · rk. See T. W. Hungerford [11]. The 13th century Chinese algebraist Ch’in Chiu-Shao used the Euclidean algorithm in his solution of the Chinese Remainder Theorem (1247) (published in Shu-shu Chiu Chang, a mathematical treatise in 9 sections).
