CONGRUENCES 109

the given modulus, and the totality of all integers congruent
to each other for a particular modulus are said to comprise
the residue class for that modulus.

From the definition, two numbers are congruent to each
other for a specified modulus when their remainders are
identical, and it therefore follows that the difference between
the two congruent numbers must be exactly divisible by the
modulus. That is, if a=b(mod m) then (a—b) must be
divisible by m.

Another development of the congruence e=b(mod m) is
that a"=b"(mod m).

Thus, 4 =7(mod 3)
and 4?=7%*'mod 3)

as will be seen by inspection. This further congruence arises
because:

4 =3+1
and 7 =(2)(3)+1
SO 4?=(3+1)?=324(2)(3) +1
and 72=(6+1)2=62+(2)(6) +1

and both of these extensions clearly differ by 1 from multiples
of 3.

This fact enables us to ascertain by a very short process
what remainder will be left when a number, expressed as a
power of a smaller number, is divided by a third number.
There is not even any need to calculate the full digital
representation of the original number. As an example we
show the procedure for finding the remainder when 22 is
divided by 15.

i 2¢ =16 and 16=1(mod 15)

therefore 2% =1(mod 15)
and (2%)"=1"(mod 15)
SO 2% =1(mod 15)

and the remainder will therefore be 1.
An important use of the congruence concept has already
been shown in Chapter 6, for the tests of divisibility included

.
|
g
P
:
g
: