160 III More on Divisibility
We turn now from the primality of 2m−1 to the primality of 2m+1. It is easily
seen that if 2m+1 is prime for somem∈N,thenmmust be a power of 2. For, if
m=rs,wherer>1 is odd, then witha= 2 swe have
2 m+ 1 =ar+ 1 =(a+ 1 )(ar−^1 −ar−^2 +···+ 1 ).PutFn:= 22n
+1. Thus, in particular,
F 0 = 3 , F 1 = 5 , F 2 = 17 , F 3 = 257 , F 4 = 65537.EvidentlyFn+ 1 − 2 =(Fn− 2 )Fn, from which it follows by induction that
Fn− 2 =F 0 F 1 ···Fn− 1 (n≥ 1 ).SinceFnis odd, this implies that(Fm,Fn)=1ifm=n. As a byproduct, we have a
proof that there are infinitely many primes.
It is easily verified thatFnitself is prime forn≤4. It was conjectured by Fermat
that the ‘Fermat numbers’Fnare all prime. However, this was disproved by Euler, who
showed that 641 dividesF 5. In fact
641 = 5 · 27 + 1 = 54 + 24.Thus 5· 27 ≡−1 mod 641 and hence 2^32 ≡− 54 · 228 ≡−(− 1 )^4 ≡−1 mod 641.
Fermat may have been as wrong as possible, since noFnwithn>4 is known
to be prime, although many have been proved to be composite. The Fermat numbers
whichareprime found an unexpected application to the construction of regular poly-
gons by ruler and compass, the only instruments which Euclid allowed himself. It was
shown by Gauss, at the age of 19, that a regular polygon ofmsides can be constructed
by ruler and compass if the orderφ(m)ofZ×(m)is a power of 2. It follows from the
formulaφ(pα)=pα−^1 (p− 1 ), and the multiplicative nature of Euler’s function, that
φ(m)is a power of 2 if and only ifmhas the form 2k·p 1 ···ps,wherek≥0and
p 1 ,...,psare distinct Fermat primes. (Wantzel (1837) showed that a regular polygon
ofmsides cannot be constructed by ruler and compass unlessmhas this form.) Gauss’s
result, in which he took particular pride, was a forerunner of Galois theory and is today
usually established as an application of that theory.
The factor 641 ofF 5 is not found simply by guesswork. Indeed, we now show that
any divisor ofFnmust be congruent to 1 mod 2n+^1. It is sufficient to establish this for
prime divisors. But ifpis a prime divisor ofFn,then2^2
n
≡−1modpand hence
22
n+ 1
≡1modp. Thus the order of 2 inF×pis exactly 2n+^1. Hence 2n+^1 dividesp− 1
andp≡1mod2n+^1.
With a little more effort we can show that any divisor ofFnmust be congruent to
1mod2n+^2 ifn>1. For, ifpis a prime divisor ofFnandn>1, thenp≡1mod8
by what we have already proved. Hence, by Proposition II.30, 2 is a quadratic residue
ofp. Thus there exists an integerasuch thata^2 ≡2modp.Sincea^2
n+ 1
≡−1modp
anda^2
n+ 2
≡1modp, the order ofainF×pis exactly 2n+^2 and hence 2n+^2 dividesp−1.
It follows from the preceding result that 641 is the first possible candidate for a
prime divisor ofF 5 , since 128k+1 is not prime fork = 1 , 3 ,4 and 257= F 3 is
relatively prime toF 5.
The hunt for Fermat primes today uses supercomputers and the following test due
to P ́epin (1877):