CONGRUENCE 21

For example, 3 =1 (mod 2)
5 =1 (mod 2)
22 =1 (mod 3)
4> =1 (mod 3)
52 =1 (mod 3)
24 =1 (mod 5)
3*=1 (mod 5)
4* =1 (mod 5)
26 =1 (mod 7)

108 = 1 (mod 7)
20= 1 (mod 11)

(— 2)22= 1 (mod 13)

302. Th. If m is a positiv prime number and a —>> m, then
am = a (mod m).

This follows easily from Fermat’s theorem by § 212.

Also Fermat’s theorem may be proved from this theorem

by § 281.
For example, 25= 2 (mod 5)
3= 3 (mod))
8 = 8 (mod7)
(—6)"= — 6 (mod 7)

303. Th. Ifa,m,and x are positiv integers, a®* = 1 (mod m),
k a positiv or zero integer, and k => x, then a* = 1 (mod m).

Since k >> x, k = gx, where ¢ is a positiv or zero integer.

Hence af = a%* = (a*)? = 12 (mod m) § 219.

For example, 52 = 1 (mod 3)
Hence 5¢ = 1 (mod 3), 5¢ = 1 (mod 3).

304. Th. Ifa,m,and x are positiv integers, a* = 1 (mod m),
k and I positiv or zero integers, and k = 1 (mod x),
then a* = a' (mod m).

Suppose £k = 1. Then k& — [ is positiv or zero.

Sincek =17l (modx), ke —1>«x '
1 (mod m) § 303.

Hence, since a* = 1 (mod m), a*!=
Hence a*t.q! = @' (mod m) §212.
Or a* = a' (mod m)