000RM.dvi

602 Infinitude of prime numbers

21.1 Proofs by construction of sequence of relatively

prime numbers

Fibonacci numbers^1

Sincegcd(Fm,Fn)=Fgcd(m,n), if there are only finitely many primesp 1 ,
...,pk, then the primes inFp 1 ,...,Fpkare distinct, and each one of them
has only one prime divisors. This contradictsF 19 = 4181 = 37× 113.

Fermat numbers

The Fermat numbers areFn:= 2^2

n
+1. It is well known that Fermat’s
conjecture of the primality ofFnis wrong. While

F 0 =3,F 1 =5,F 2 =17,F 3 = 257,F 4 = 65537

are all primes, Euler found that

F 5 =2^32 + 1 = 4294967297 = 641× 6700417.

Note that

Fn−2=2^2

n

−1=

(

22

n− 1

+1

)(

22

n− 1

− 1

)

=Fn− 1 (Fn− 1 −2).

By induction,

Fn=Fn− 1 Fn− 2 ···F 1 ·F 0 +2,n≥ 1.

From this, we see thatFndoes not contain any factor ofF 0 ,F 1 , ...,
Fn− 1. Hence, the Fermat numbers are pairwise relatively prime. From
this, it follows that there are infinitely primes.

(^1) M. Wunderlich, Another proof of the infinite primes theorem,American Math. Monthly, 72 (1965) 305.