CHAP. 11] PROPERTIES OF THE INTEGERS 277
Cancellation Laws for Congruences
Recall that the integers satisfy the following:Cancellation law: Ifab=acanda=0, thenb=c.The critical difference between ordinary arithmetic and arithmetic modulomis that the above cancellation
law is not true for congruences. For example,
3 · 1 ≡ 3 · 5 (mod 6) but 1= 5 (mod 6)That is, we cannot cancel the 3 even though 3≡0 (mod 6). However, we do have the followingModified
Cancellation Lawfor our congruence relations.
Theorem 11.23 (Modified Cancellation Law): Supposeab≡ac(modm) and gcd(a, m)= 1.
Thenb≡c(modm).The above theorem is a consequence of the following more general result (proved in Problem 11.37).Theorem 11.24: Supposeab≡ac(modm) andd=gcd(a, m). Thenb≡c(modm/d).
EXAMPLE 11.13Consider the following congruence:6 ≡ 36 (mod 10) (11.1)Since gcd( 3 , 10 )=1 but gcd( 6 , 10 )=1, we can divide both sides of (11.1) by 3 but not by 6. That is,2 ≡ 12 (mod 10) but 1≡ 6 (mod 10 )However, by Theorem 11.24, we can divide both sides of (11.1) by 6 if we also divide the modulus by 2 which
equals gcd(6, 10). That is,
1 ≡ 6 (mod 5)
Remark:Supposepis a prime. Then the integers 1 throughp−1 are relatively prime top. Thus the usual
cancellation law does hold when the modulus is a primep. That is:
Ifab≡ac (modp)anda = 0 (modp),thenb≡c(modp).ThusZp, the integers modulo a primep, plays a very special role in number theory.
Reduced Residue Systems, Euler Phi Function
The modified cancellation law, Theorem 11.23, is indicative of the special role played by those integers which
are relatively prime (coprime) to the modulusm. We note thatais coprime tomif and only if every element
in the residue class [a] is coprime tom. Thus we can speak of a residue class being coprime tom.
The number of residue classes relatively prime tomor, equivalently, the number of integers between 1 and
m(inclusive) which are relatively prime tomis denoted by
φ(m)The functionφ(m)is called theEuler phi function. The list of numbers between 1 andmwhich are coprime to
mor, more generally, any list ofφ(m)incongruent integers which are coprime tom, is called areduced residue
system modulom.