TR

AT

AT s

e

PPV P SR (RN e i

=

5

(§
1
S
N
=
|

%‘::— }
=
-
-_I |
-
£ i
E
§
i
g
;
=
é
.

 

IIO THE FASCINATION OF NUMBERS

are all based on the conversion of certain numbers into the
form of multiples of other numbers plus certain remainders.
Congruences also assist in certain other cases of factorization.
We can, for example, prove that the number 23 is a factor of
the expression 21t —1 as follows:

25=g2=9(mod 23)
Therefore, by squaring each side of the congruence,
219=81(mod 23)
=12(mod 23)
(12 being the new remainder when 81 is divided by 23, so
that 81=12(mod 23).

But 2=2(mod 23)
SO 210 x 2=12 X 2(mod 23)
or 211=24(mod 23)
=1(mod 23)
since 24=1(mod 23)

Therefore, when 21*—1 is divided by 23 there is no re-
mainder, and accordingly 23 must be a factor of 211 —1.

When dealing with residue classes to the same modulus,
the multiplication of two terms involves the multiplication of
their respective remainders.

16=2(mod 14)

and 18=4(mod 14)
SO 16 X 18=2 X 4(mod 14)
=8(mod 14)

It is important to note, however, that the reverse procedure
is not necessarily correct for all congruences. Whilst the
element 8(mod 14) can, by reversing the above procedure,
be split into two elements 2(mod 14) and 4(mod 14), no
similar procedure can be employed in all cases.

The number 16 is, for instance, congruent to 6 for the
modulus 10, but it is not possible to split the element 6 into
two factors so as to give two relative residues whose multi-
plication would give a result congruent to 6(mod 10). If we
take the factors g and 2 of the element 6, one of the residues