Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

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.
```
Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search