SECTION 2.1 Elementary Number Theory 89
(a) Sinceφ(n)< nfor alln, we see that the sequencea 1 , a 2 , ...,
eventually becomes constant moduloφ(n).
(b) Writen = 2rk, wherek is an odd integer. Since a 1 , a 2 , ...,
eventually becomes constant moduloφ(n), it also eventually
becomes constant moduloφ(k).
(c) Conclude from Euler’s Theorem (87) thata 1 , a 2 , ..., eventu-
ally becomes constant modulok.
(d) Argue that a 1 , a 2 , ..., eventually becomes constant modulo
2 rand hence eventually becomes constant modulon.2.1.7 Linear congruences
A linear congruence is of the form ax ≡ b(mod n), where a, b, n are
integers,n >0, andx is regarded as unknown. In order to solve this
equation, we would hope thata would have an inverse modulo n. In
other would if there exists an integera′such thata′a≡1(modn), then
we can solve the above congruence by multiplying through bya′:
x≡a′b(modn).Next, if a andnare relatively prime, then we can employ the Eu-
clidean trick and write
sa+tn= 1,for suitable integerssandt. But this says already that
sa= 1−tn≡1(modn),i.e., thata′=sis the desired inverse ofamodulon.
Example. Solve the congruence 5x≡14(mod 18).
Solution. We employ the Euclidean algorithm: