98 6. Integers, Divisors, and Primes
Herepdivides the numerator, but not the denominator, since all factors in
the denominator are smaller thanp, and we know by Exercise 6.3.3(a) that
if a primepdoes not divide any of these factors, then it does not divide
the product. Hence it follows (see Exercise 6.3.3(b)) that( pis a divisor of
p
k
)
.
Proof[of Theorem 6.5.1]. Now we can prove Fermat’s Theorem by induc-
tion ona. The assertion is trivially true ifa= 0. Leta>0, and write
a=b+ 1. Then
ap−a=(b+1)p−(b+1)=bp+(
p
1)
bp−^1 +···+(
p
p− 1)
b+1−b− 1=(bp−b)+(
p
1)
bp−^1 +···+(
p
p− 1)
b.Here the expressionbp−bin parenthesis is divisible bypby the induction
hypothesis, while the other terms are divisible bypby lemma 6.5.2. It
follows thatap−ais also divisible byp, which completes the induction.
Let us make a remark about the history of mathematics here. Fermat is
most famous for his “last” Theorem, which is the following assertion:
Ifn> 2 , then the sum of thenth powers of two positive integers
is never thenth power of a positive integer.(The assumption thatn>2 is essential: There are examples of two squares
whose sum is a third square. For example, 3^2 +4^2 =5^2 ,or5^2 +12^2 =13^2.
In fact, there are infinitely many such triples of squares, see Exercise 6.6.7.)
Fermat claimed in a note that he had proved this, but never wrote down
the proof. This statement remained perhaps the most famous unsolved
problem in mathematics until 1995, when Andrew Wiles (in one part with
the help of Robert Taylor) finally proved it.
6.5.1Show by examples that neither the assertion in lemma 6.5.2 nor Fermat’s
“Little” Theorem remains valid if we drop the assumption thatpis a prime.
6.5.2Consider a regularp-gon, and for a fixedk(1≤k≤p−1), consider all
k-subsets of the set of its vertices. Put all thesek-subsets into a number of boxes:
We put twok-subsets into the same box if they can be rotated into each other.
For example, allk-subsets consisting ofkconsecutive vertices will belong to one
and the same box.
(a) Prove that ifpis a prime, then each box will contain exactlypof these
rotated copies.
(b) Show by an example that (a) does not remain true if we drop the assump-
tion thatpis a prime.