Number Theory: An Introduction to Mathematics

5 Congruences 107

equality (but coincides with it ifm=0). The corresponding equivalence classes are
calledresidue classes.ThesetZwith equality replaced by congruence modmwill be
denoted byZ(m).Ifm>0,Z(m)has cardinalitym, since an arbitrary integeracan be
uniquely represented in the forma=qm+r,wherer∈{ 0 , 1 ,...,m− 1 }andq∈Z.
The particularrwhich represents a givena∈Zis referred to as theleast non-negative
residueofamodm.
The replacement laws imply that the associative, commutative and distributive laws
for addition and multiplication are inherited fromZbyZ(m). HenceZ(m)is a commu-
tative ring, with 0 as an identity element for addition and 1 as an identity element for
multiplication. However,Z(m)is not an integral domain ifmis composite, since if
m=m′m′′with 1<m′<m,then

m′m′′≡ 0 ,butm′≡ 0 ,m′′≡0modm.

On the other hand, ifab≡acmodmand(a,m)=1, thenb≡cmodm, by Proposi-
tion 3(ii). Thus factors which are relatively prime to the modulus can be cancelled.
In algebraic terms,Z(m)is thequotient ringZ/mZofZwith respect to the ideal
mZgenerated bym, and the elements ofZ(m)are thecosetsof this ideal. For conve-
nience, rather than necessity, we suppose from now on thatm>1.
Congruences enter implicitly into many everyday problems. For example, the ring
Z( 2 )contains two distinct elements, 0 and 1, with the addition and multiplication tables

0 + 0 = 1 + 1 = 0 , 0 + 1 = 1 + 0 = 1 ,

0 · 0 = 0 · 1 = 1 · 0 = 0 , 1 · 1 = 1.

This is the arithmetic ofodds(1) andevens(0), which is used by electronic computers.
Again, to determine the day of the week on which one was born, from the date and
day of the week today, is an easy calculation in the arithmetic ofZ( 7 )(remembering
that 366≡2 mod 7).
The well-known tests for divisibility of an integer by 3 or 9 are easily derived by
means of congruences. Let the positive integerahave the decimal representation

a=a 0 +a 110 +···+an 10 n,

wherea 0 ,a 1 ,...,an∈{ 0 , 1 ,..., 9 }.Since10≡1modm,wherem=3or9,the
replacement laws imply that 10k≡1modmfor any positive integerkand hence

a≡a 0 +a 1 +···+anmodm.

Thusais divisible by 3 or 9 if and only if the sum of its digits is so divisible.
This can be used to check the accuracy ofarithmetical calculations. Any equa-
tion involving only additions and multiplications must remain valid when equality is
replaced by congruence modm. For example, suppose we wish to check if

7714 × 3036 = 23 , 419 , 804.

Taking congruences mod 9, we have on the left side 19× 12 ≡ 1 × 3 ≡3 and on the
right side 5+ 14 + 12 ≡ 5 + 5 + 3 ≡4. Since 4≡3 mod 9, the original equation is
incorrect (the 8 should be a 7).