Fermat Numbers Problems

**1337h4x** · May 14th 2010, 09:25 AM

Hello all, I'm trying to learn more about Fermat Numbers. My textbook claims that:

Fermat Numbers are defined by F[m]= (2^(2^m)) + 1. It says that it can be problem that for m!=n that (F[m],F[n])=1 , where [ ] denotes subscripts.

It says the proof involved first proving F[m+1]=F[0]*F[1]*...*F[m]+2 , and that this can be proved by trying to represent F[m+1] in terms of F[m]. How does this work?

Next question (related):

My book also says that by assuming that the Fermat Numbers F[m] are pairwise relatively prime, that we can prove that there are infinitely primes. It says this can be proved only involving the result that the Fermat numbers are pairwise relatively prime. It says the result is the only thing utilized and not the details of the proof. Can anyone explain how this is actually proven?

Much thanks!

**undefined** · May 14th 2010, 09:40 AM

Originally Posted by 1337h4x

Fermat Numbers are defined by F[m]= (2^(2m)) + 1.

You missed a carat symbol, and I initially got an incorrect result based on your definition (didn't take long though). It should be

$F_m=2^{2^m}+1$

Originally Posted by 1337h4x

...and that this can be proved by trying to represent F[m+1] in terms of F[m]

This part is easy to derive

$F_{m+1}=2^{2^{m+1}}+1 = 2^{2 \cdot 2^m}+1$

$=\left(2^{2^m}\right)^2+1$

$=(F_m-1)^2+1$

Haven't worked on the rest of the problem.. I won't have time today, so I'm guessing by the time I would be able to work on everything else, someone will already have addressed it.

**1337h4x** · May 14th 2010, 09:50 AM

Originally Posted by undefined

You missed a carat symbol, and I initially got an incorrect result based on your definition (didn't take long though). It should be

$F_m=2^{2^m}+1$

This part is easy to derive

$F_{m+1}=2^{2^{m+1}}+1 = 2^{2 \cdot 2^m}+1$

$=\left(2^{2^m}\right)^2+1$

$=(F_m-1)^2+1$

Haven't worked on the rest of the problem.. I won't have time today, so I'm guessing by the time I would be able to work on everything else, someone will already have addressed it.

I understand your reasoning thus far. I do need someone else to help explain where to go from here.

**undefined** · May 14th 2010, 10:45 AM

Originally Posted by 1337h4x

I understand your reasoning thus far. I do need someone else to help explain where to go from here.

Hm, found some time to go a bit further.

$F_{m+1}=(F_m-1)^2+1$

$=F_m^2-2F_m+2$

$=F_m(F_m-2)+2$

Replace as follows

$F_{m+1}=F_m(\color{red}F_m\color{black}-2)+2$

$=F_m(\color{red}F_{m-1}(F_{m-1}-2)+2\color{black}-2)+2$

$=F_mF_{m-1}(F_{m-1}-2)+2$

Eventually we reach $F_0=3$ and the expression in parentheses vanishes, giving the desired result. This could be proven more rigorously with induction.

**1337h4x** · May 14th 2010, 11:15 AM

Originally Posted by undefined

Hm, found some time to go a bit further.

$F_{m+1}=(F_m-1)^2+1$

$=F_m^2-2F_m+2$

$=F_m(F_m-2)+2$

Replace as follows

$F_{m+1}=F_m(\color{red}F_m\color{black}-2)+2$

$=F_m(\color{red}F_{m-1}(F_{m-1}-2)+2\color{black}-2)+2$

$=F_mF_{m-1}(F_{m-1}-2)+2$

Eventually we reach $F_0=3$ and the expression in parentheses vanishes, giving the desired result. This could be proven more rigorously with induction.

Can you explain how we reach $F_0=3$ ? I follow you all the way up to that.

**undefined** · May 14th 2010, 11:25 AM

Ah, m!=n means $m \neq n$ . I originally misinterpreted as $m! = n$ .

There is a very easy proof in this Wikipedia article; look for Goldbach's theorem, under Basic properties.

As for the infinitude of primes, consider that the sequence $F_m$ produces an infinite number of pairwise coprime numbers. Suppose there exist only a finite number of primes. Then each prime can be associated with (by divisibility) at most one element from $F_m$ . Intuitively, we see the result already, but formally we may introduce a function f: A -> B where A is the set of all primes that divide some Fermat number (by assumption, A is finite) and B is the set of all Fermat numbers. Then clearly f cannot be a surjection (because the cardinality of B is greater than the cardinality of A), and thus there exist Fermat numbers with no prime factors, which is a contradiction.

Edit: Hmm, two points I didn't consider:

1) I'm not sure how the Wikipedia proof was able to derive that $a$ divides $F_0 \cdots F_{j-1}$ . I suppose it's correct and obvious and I'm just missing the reasoning behind it. (Some minutes later) Oh right it's so obvious. $F_i$ is one of the factors in $F_0 \cdots F_{j-1}$ . Sometimes I'm just really slow. :-/

2) I didn't notice the Wikipedia article gave that the infinitude of primes is a corollary of Goldbach's theorem, with a much shorter proof than mine.

**undefined** · May 14th 2010, 11:34 AM

Originally Posted by 1337h4x

Can you explain how we reach $F_0=3$ ? I follow you all the way up to that.

Starting from

$F_{m+1}=F_mF_{m-1}(F_{m-1}-2)+2$

we can continue substituting

$F_{m+1}=F_mF_{m-1}(\color{red}F_{m-1}\color{black}-2)+2$

$=F_mF_{m-1}(\color{red}F_{m-2}(F_{m-2}-2)+2\color{black}-2)+2$

$=F_mF_{m-1}F_{m-2}(F_{m-2}-2)+2$

We continue until reaching $F_0=2^{2^0}+1=2^1+1=3$ .

Thread: Fermat Numbers Problems

LinkBack

Thread Tools

Display

Fermat Numbers Problems

Similar Math Help Forum Discussions

Questions about Fermat numbers?

Infinity of primes through fermat numbers

Complex numbers problems......

Two problems with Fermat and Wilson

Complex numbers: 2 problems.

Search Tags