106 6. Integers, Divisors, and Primes
andtransitivity,
a≡b (modm),b≡c (modm)=⇒ a≡c (modm).These are trivial if we think of the congruence relation as claiming equality:
namely, equality of the remainders when divided bym.
We can compute with congruences just as we can with equations. If we
have two congruences with the same modulus,
a≡b (modm) and c≡d (modm),then we can add them, subtract them, and multiply them to get
a+c≡b+d (modm),a−c≡b−d (modm),ac≡bd (modm)(we’ll return to division later). A useful special case of the multiplication
rule is that we can multiply both sides of a congruence by the same number:
ifa≡b(modm), thenka≡kb(modm) for every integerk.
These properties need to be proved, however. By hypothesis,a−band
c−dare divisible bym. To see that congruences can be added, we must
verify that (a+c)−(b+d) is divisible bym. To this end, we write it in
the form (a−b)+(c−d), which shows that it is the sum of two integers
divisible bymand so it is also divisible bym.
The proof that congruences can be subtracted is very similar, but mul-
tiplication is a bit trickier. We have to show thatac−bdis divisible bym.
To this end, we write it in the form
ac−bd=(a−b)c+b(c−d).Herea−bandc−dare divisible bym, and hence so are (a−b)cand
b(c−d), and hence so is their sum.
The congruence notation is very convenient in formulating various state-
ments and arguments about divisibility. For example, Fermat’s Theorem
(Theorem 6.5.1) can be stated as follows: Ifpis a prime then
ap≡a (modp).6.7.1What is the largest integermfor which 12345≡54321 (modm)?6.7.2Which of the following “rules” are true?
(a)a≡b (modc) ⇒ a+x≡b+x (modc+x);
(b) a≡b (modc) ⇒ ax≡bx (modcx).(c)
a≡b (modc)
x≡y (modz)
⇒ a+x≡b+y (modc+z);(d) a≡b (modc)
x≡y (modz)
⇒ ax≡by (modcz).