88 SPECIAL TOPICS IN THEORETICAL ARITHMETIC

196. Th. a =0 (modm) DaX@m = bR m

For by § 195 any common factor of 4 and m is a factor of a
and therfor a common factor of ¢ and .

Similarly any common factor of @ and m is a common factor
of b and m.

Therfor the common factors of @ and m are the same set
of numbers as the common factors of b and .

Therfor the greatest common factor of ¢ and m is the same
as the greatest common factor of b and .

197. Th. a=0b (modm) ~b 1l m D a || m.
This follows immediately from the preceding theorem and
§ 171,

198. Th. a+ 1]] a

If @ = 0, this follows from § 160.

Suppose @ —= 0.

Thenae +1 =1 (moda) ~1]] a. §§ 176, 160.
Therfor a + 1 ]| a. § 197.

199. Th. a + Im = a (mod m)

In words: If any multiple of the modulus is added to an
integer, the sum is congruent to the integer.

For (¢ +1m) —a =lm > m

200. Th. @ — Im = a (mod m)

201. Th. a=b(modm) Da—km=>b—Im
Fora —km=a=b=0b—Im

202. Th. Any integer is congruent to every remainder 0b-
taind when it is divided by the modulus, and conversely, if
a = r (mod m), then r is a remainder obtaind by dividing a by m.

For the direct theorem, if 7 is a remainder and ¢ the corre-
sponding quotient, when « is divided by m,
then a = qgm + 7. §§ 77, 91.

But gm + r = r (mod m) § 199.

Therfor a = r (mod m)