Fermat Numbers

Date: 01/25/2003 at 14:13:49
From: Ghori
Subject: Fermat Number

How can we prove that any two Fermat Numbers are coprime?

Date: 01/25/2003 at 23:19:33
From: Doctor Paul
Subject: Re: Fermat Number

First establish by induction the following identity:

[F_0 * F_1 * F_2 * ... * F_(n-1)] + 2 = F_n. 

Then we have:

F_0 * F_1 * F_2 * ... * F_(n-1) = F_n - 2

Now suppose that there exists some integer d > 1 that divides both 
F_n and F_m for some m < n.

Since d divides F_m for some m < n, it is clear that d also divides 
F_0 * F_1 * F_2 * ... * F_(n-1)

But since F_0 * F_1 * F_2 * ... * F_(n-1) = F_n - 2, we can say that 
d must divide F_n - 2.  We assumed above that d divides F_n.  This, 
coupled with the fact that d divides F_n - 2 implies that d divides 
two.  So either d = 2 or d = 1.

But every Fermat number is odd. Thus it cannot be the case that d = 2.  
Hence d = 1. This contradicts the assumption that d > 1. Since this 
contradiction was derived directly from the assumption, it must be the 
case that our assumption is false.  Thus no such d > 1 exists and it
in fact is the case that the Fermat numbers are pairwise relatively 
prime.

I hope this helps. Please write back if you'd like to talk about 
this some more.

- Doctor Paul, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 01/26/2003 at 07:18:19
From: Ghori
Subject: Fermat Number

Dear Paul,

Thanks for this lovely proof. But how can we establish the following 
identity.

[F_0 * F_1 * F_2 * ... * F_(n-1)] + 2 = F_n.

Best Regards
Ghori

Date: 01/26/2003 at 10:37:29
From: Doctor Paul
Subject: Re: Fermat Number

Proceed by induction on n.

If n = 1, the equation yields 3 + 2 = 5 which is clearly true.

Now assume that [F_0 * F_1 * F_2 * ... * F_(n-1)] + 2 = F_n. 

We want to prove:

[F_0 * F_1 * F_2 * F_(n-1) * F_n] + 2 = F_(n+1). 

To do this, proceed as follows:

Let x = [F_0 * F_1 * F_2 * ... * F_(n-1)]

and 

let y = [F_0 * F_1 * F_2 * ... * F_(n-1) * F_n]

Then we want to prove that

y + 2 = F_(n+1)

Notice that y = x * (x+2).  This follows directly from the inductive 
hypothesis.

So we want to show that

[x * (x+2)] + 2 = F_(n+1)

Now,

[x * (x+2)] + 2

Notice that by the inductive hypothesis, we have:  x = F_n - 2

Thus [x * (x+2)] + 2 = [(F_n - 2) * ((F_n - 2) + 2)] + 2 = 

[(F_n - 2) * F_n] + 2 = 

(F_n)^2 - 2*F_n + 2 = 

(2^(2^n) + 1) * (2^(2^n) + 1) - 2 * (2^(2^n) + 1) + 2 = 

2^(2^n) * 2^(2^n) + 2 * 2^(2^n) + 1 - 2 * 2^(2^n) - 2 + 2 = 

2^(2^n) * 2^(2^n) + 1 = 

2^(2^n + 2^n) + 1 = 

2^(2*(2^n)) + 1 = 

2^(2^(n+1)) + 1 = 

F_(n+1)

I hope this helps.  Please write back if you'd like to talk about 
this some more.

- Doctor Paul, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 01/27/2003 at 04:14:31
From: Ghori
Subject: Fermat Numbers

Are there infinitely many Fermat Numbers? How do we know that each 
Fermat Number will have a prime divisor?

Date: 01/27/2003 at 18:34:27
From: Doctor Paul
Subject: Re: Fermat Numbers

The Fermat numbers are defined by:

F_n = 2^(2^n)) + 1

Inasmuch as there are infinitely many positive integers that we can 
choose as the value for n, there are infinitely many Fermat numbers.

By the Fundamental Theorem of Arithmetic, we know that each positive 
integer can be uniquely decomposed into a product of primes. The fact 
that F_n can be thus decomposed is all we need to guarantee the 
existence of a prime divisor of F_n for all positive integers n.

You asked previously:

   If P_n is the n-th prime, how can we show that P_n <= F_n ?

One of the other math doctors noticed:

P_n has to be less than F_n because a prime dividing F_n is P_m, 
where m is at least n, since there are certainly primes that divide 
no Fermat prime (e.g. 2).

I hope this helps.  Please write back if you'd like to talk about 
this some more.

- Doctor Paul, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 01/28/2003 at 16:53:20
From: Ghori
Subject: Fermat Number

Again thanks for your sincere response. I have never seen any 
volunteer academic service better than "Ask Dr Math." It is really a 
very great service. It would be unfair if I did not appreciate the 
people who provide this service. Of course, this service has promoted 
the awareness and importance of Mathematics.