72 CHAPTER 2 Discrete Mathematics
Therefore, d = gcd(1832,2417) = 1; working backwards through the
above yields
157 · 1832 − 119 · 2417(sos= 157 andt=−119). We have 234−1099 =−865 =zand so a
solution is given bym=x−sza= 234 + 157· 865 ·1832 = 248, 794 , 994.
Finally, any other solutionm′will be congruent to 248,794,994 modulo
l = lcm(1832,2417) = 1832·2417 = 4, 427 ,944. We therefore reduce
248,794,994 modulolusing the division algorithm:
248 , 794 ,994 = 56· 4 , 427 ,944 = 830, 130 ,and so the least integer solution ism= 830, 130.
Example 3. In this example we indicate a solution of three congru-
ences. From this, the student should have no difficulty in solving more
than three congruences, including the lead problem in this subsection.
Find the least positive solution of the congruences
m ≡ 1(mod 6)
m ≡ 7(mod 15)
m ≡ 4(mod 19).First, we have
1 · 15 − 2 ·6 = 3
from which we conclude that 3 = gcd(6,15). Next, we have 7−1 = 2·3,
and so
2 · 15 − 2 · 2 ·6 = 2·3 = 7−1;this tells us to set m 1 = 1− 2 · 2 ·6 = 7− 2 ·15 = −23. We have
already seen that all solutions will be congruent to−23 modulo l 1 =
lcm(6,15) = 30. Therefore, the least positive solution will be m 1 = 7
(which could have probably more easily been found just by inspection!).
Note that ifmis integer satisfyingm≡7(mod 30), then of course we
also havem ≡ 7(mod 6) andm ≡7(mod 15), and so m ≡1(mod 6)
and m ≡ 7(mod 15). Therefore, we need to find the least positive
integer solution of