Tag Archives: Pépin’s test

Fermat Numbers

Posted on by

Fermat Number, a class of numbers, is an integer of the form F_n=2^{2^n} +1 \ \ n \ge 0.

For example: Putting n := 0,1,2 \ldots in F_n=2^{2^n} we get F_0=3, F_1=5, F_2=17, F_3=257 etc.

Fermat observed that all the integers F_0, F_1, F_2, F_3, \ldots were prime numbers and announced that F_n is a prime for each natural value of n.

In writing to Prof. Mersenne, Fermat confidently announced:

I have found that numbers of the form 2^{2^n}+1 are always prime numbers and have long since signified to analysts the truth of this theorem.

However, he also accepted that he was unable to prove it theoretically. Euler in 1732 negated Fermat’s fact and told that F_1 -F_4 are primes but F_5=2^{2^5} =4294967297 is not a prime since it is divisible by 641.
Euler also stated that all Fermat numbers are not necessarily primes and the Fermat number which is a prime, might be called a Fermat Prime. Euler used division to prove the fact that F_5 is not a prime. The elementary proof of Euler’s negation is due to G. Bennett.

Theorem:
The Fermat number F_5 is divisible by 641 i.e., 641|F_5.

Proof:

As defined F_5 :=2^{2^5}+1=2^{32}+1 \ \ldots (1)

Factorising 641 in such a way that 641=640+1 =5 \times 128+1 \\ =5 \times 2^7 +1
Assuming a=5 \bigwedge b=2^7 we have ab+1=641.

Subtracting a^4=5^4=625 from 641, we get ab+1-a^4=641-625=16=2^4 \ \ldots (2).

Now again, equation (1) could be written as
F_5=2^{32}+1 \\ \ =2^4 \times {(2^7)}^4+1 \\ \ =2^4 b^4 +1 \\ \ =(1+ab-a^4)b^4 +1 \\ \ =(1+ab)[a^4+(1-ab)(1+a^2b^2)] \\ \ =641 \times \mathrm{an \, Integer}
Which gives that 641|F_n.

Mathematics is on its progression and well developed now but it is yet not confirmed that whether there are infinitely many Fermat primes or, for that matter, whether there is at least one Fermat prime beyond F_4. The best guess is that all Fermat numbers F_n>F_4 are composite (non-prime).
A useful property of Fermat numbers is that they are relatively prime to each other; i.e., for Fermat numbers F_n, F_m \ m > n \ge 0, \mathrm{gcd}(F_m, F_n) =1.

Following two theorems are very useful in determining the primality of Fermat numbers:

Pepin Test:
For n \ge 1, the Fermat number F_n is prime \iff 3^{(F_n-1)/2} \equiv -1 \pmod {F_n}

Euler- Lucas Theorem
Any prime divisor p of F_n, where n \ge 2, is of form p=k \cdot 2^{n+2}+1.

Fermat numbers (F_n) with n=0, 1, 2, 3, 4 are prime; with n=5,6,7,8,9,10,11 have completely been factored; with n=12, 13, 15, 16, 18, 19, 25, 27, 30 have two or more prime factors known; with n=17, 21, 23, 26, 28, 29, 31, 32 have only one prime factor known; with n=14,20,22,24 have no factors known but proved composites. F_{33} has not yet been proved either prime or composite.

Related articles