SECTION 2.1 Elementary Number Theory 87
above observation. Note first that it suffices to assume thata≥1; we
shall argue by induction ona. Note that ifa= 1 the result is clearly
valid. Next, assuming thata >1, then by induction we may assume
that (a−1)p≡(a−1)(modp). From this we proceed:
ap ≡ ((a−1) + 1)p
≡ (a−1)p+ 1p (by the above result)
≡ a−1 + 1 (by induction)
≡ a(modp),which completes the proof.
There is a striking generalization of Fermat’s Little Theorem, as
follows. I won’t prove this here as the most natural proof of this is
within the context of group theory. Anyway, recall the Eulerφ-function
(see Exercise 16 on page 63), defined by setting
φ(n) = # of integersm, 1 ≤m < nwhich are relatively prime withn.
This obviously says, in particular that ifpis prime thenφ(p) =p− 1.
Theorem. (Euler’s Theorem)Letnbe any positive integer. Then for
any integera withgcd(a,n) = 1we have
aφ(n)≡1(modn).Note that Euler’s Theorem obviously contains Fermat’s Little Theorem
as a corollary.
Exercises
- Compute the units digit of (23)^987
- Compute the least positive integer solution ofn≡ 123139 (mod 7).
- Compute the least positive integer solution ofn≡ 50610
6
(mod 11).