CONGRUENCE 15t

Thus addition, subtraction, and multiplication can be easily
checkt by congruences.

The checking of division is a trifle more complicated.

Let a be the dividend, b the divisor, ¢ the quotient, and 7
the remainder.

Then a = gb + r and ¢ — r = ¢b.

From either of these two formulas a congruence check for-
mula can be obtaind. We will use the first.

Suppose a = a' (mod m)
b=10
g=q
r=r
Then gb+r=qb +r
Thuswehave ¢’ =a =qgb+7=q0 + 7
Therfor a =qb + 7

This is the check formula spoken of. However this formula
may be still further simplified by replacing ¢’0’ by a number ¢
to which it may be congruent and then the sum of ¢ and #/
by a number ¢’ to which it may be congruent.

Then ¢'0' + 7 =c¢c + 7 = ¢/, whence @’ = ¢'.

As an example let us divide 347 by 27. Here ¢ = 347 and
b = 27. We find the lower quotient ¢ = 12 and the corre-
sponding remainder » = 23.

Hence 347 = 12 X 27 4 23.

If we choose the modulus 7, we find ¢’ = 4, = 6, ¢ = 5,
Vo= ol

Since @’ = ¢/, the work checks.

We may indicate the work of checking as follows:

q=12 =35 (mod 7)

b=27=6

84

24
gh =324 =30 =2
ga=03 =2
a = 347 =4