SECTION 2.1 Elementary Number Theory 71
Applying the Euclidean algorithm yields
855 = 6·138 + 27
138 = 5·27 + 3
27 = 9·3 + 0,and sod= gcd(138,855) = 3; furthermore the above shows that
3 = 138− 5 ·27 = 138−5(835− 6 ·138) = 31· 138 − 5 · 855(and sos= 31 and t=−5). Also, since 14≡23(mod 3) we conclude
that the above congruences can be solved. Indeed, 14−23 = − 3 · 3
(so z = −3) and so a solution is m = x−sza = 14 + 31· 138 ·
3 = 12,848. Finally, we can prove that 12,848 is actually the least
positive integer solution of the above congruences above, as follows.
To do this, apply the Chinese Remainder Theorem to conclude that
if m′ is any other solution, and if l = lcm(138,855) = 39,330, then
m′≡ 12 ,848(mod 39,330). This is clearly enough!
Example 2. Find the least positive integer solution of
m ≡ 234(mod 1832)
m ≡ 1099(mod 2417).This one is technically more involved. However, once one recognizes
that 2417 is a prime number, we see immediately that 2417 and 1832
are relatively prime and so at least we know that a solution exists. Now
comes the tedious part: