Infinitude of Primes
Via Fermat Numbers
The Fermat numbers form a sequence in the form Fn = 22n + 1, n = 0, 1, 2, ... Clearly all the Fermat numbers are odd. Moreover, as we'll see shortly, any two are mutually prime. In other words, each has a prime factor not shared by any other. Hence, the number of primes cannot be finite.
That no two Fermat numbers have a non-trivial common factor follows from the two lemmas below.
Lemma 1
| (1) |
F0·F1·F2·...·Fn-1 = Fn - 2, n ≥ 1.
|
Proof
The proof is by induction. Since F0 = 3 and F1 = 5, (1) is indeed true for k = 1. Assume it holds for k = n. For k = n+1,
| |
| F0·F1·F2·...·Fn | = (F0·F1·F2·...·Fn-1)·Fn |
| | = (Fn - 2)·Fn |
| | = (22n - 1)(22n + 1) |
| | = 22n+1 - 1 |
| | = Fn+1 - 2. |
|
Lemma 2
| (1) |
For n ≠ m, Fn and Fm are mutually prime.
|
Proof
Indeed, assume t divides both Fn and Fm, m < n. By Lemma 1,
| |
Fn = F0·F1·...·Fm·...·Fn-1 - 2,
|
implying that t divides
| |
F0·F1·...·Fm·...·Fn-1 - Fn = 2.
|
But 2 has only two factors: 1 and 2. Being odd, Fermat numbers are not divisible by 2. Hence t = 1, which proves the lemma.
Reference
- M. Aigner, G. Ziegler, Proofs from THE BOOK, Springer, 2000
- G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth Edition, Oxford Science Publications, 1996.
Copyright © 1996-2008 Alexander Bogomolny
|
