1. ## Fermat Numbers Problems

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!

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

$\displaystyle 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

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

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

$\displaystyle =(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.

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

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

This part is easy to derive

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

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

$\displaystyle =(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.

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

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

$\displaystyle =F_m^2-2F_m+2$

$\displaystyle =F_m(F_m-2)+2$

Replace as follows

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

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

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

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

5. Originally Posted by undefined
Hm, found some time to go a bit further.

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

$\displaystyle =F_m^2-2F_m+2$

$\displaystyle =F_m(F_m-2)+2$

Replace as follows

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

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

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

Eventually we reach $\displaystyle 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 $\displaystyle F_0=3$ ? I follow you all the way up to that.

6. Ah, m!=n means $\displaystyle m \neq n$. I originally misinterpreted as $\displaystyle 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 $\displaystyle 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 $\displaystyle 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 $\displaystyle a$ divides $\displaystyle 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. $\displaystyle F_i$ is one of the factors in $\displaystyle 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.

7. Originally Posted by 1337h4x
Can you explain how we reach $\displaystyle F_0=3$ ? I follow you all the way up to that.
Starting from

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

we can continue substituting

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

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

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

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