# Fermat number proof

1. Feb 21, 2014

### cragar

1. The problem statement, all variables and given/known data
Show that all fermat numbers are relatively prime.
3. The attempt at a solution
If they share common factors then it should divide their difference so I look at
n>x
$(2^{2^n}+1)-(2^{2^x}+1)=2^{2^x}(2^{2^n-2^x}-1)$
Now since fermat numbers are odd their factors will have to be contained in
$(2^{2^n-2^x}-1)$ Now if they share common factors then it should divide
$(2^{2^n-2^x}-1)+(2^{2^n}+1)= (2^{2^n-2^x}+2^{2^n})=2^{2^n}(2^{-2^x}+1)$
Since fermat numbers are odd their factors must divide into
$(2^{-2^x}+1)$ but this is not an integer so this contradicts our assumption that it will divide our sum, so fermat numbers are relatively prime.

2. Feb 21, 2014

### Curious3141

Looks good. The usual way to prove this is to use one of the properties of Fermat numbers, like $F_0F_1...F_{n-1} + 2 = F_n$, which gives a much quicker and neater proof. But proving that proposition is more work to begin with. So your way is better from first principles.

This webdocument is quite useful: http://modular.math.washington.edu/edu/2010/414/projects/tsang.pdf [Broken]

EDIT: Please see Joffan's and Dick's posts. You cannot use this if one (or more) of your factors is not an integer.

Last edited by a moderator: May 6, 2017
3. Feb 21, 2014

### Joffan

Sorry, no - you can't present that final step as a valid factorization with one of the parts non-integer.

4. Feb 21, 2014

### Dick

Obviously, let's prove $2^n-1$ is prime. $2^n-1=2^n(1-2^{-n})$, $2^n-1$ is odd therefore any factor must divide $1-2^{-n}$ which not an integer. QED. That's baloney. $2^4-1=15$ is not prime.

5. Feb 21, 2014

### Curious3141

A very good point. When making the argument, both factors must be integers.