Fermat Number Proof: Relatively Prime

[cragar]

Homework Statement

Show that all fermat numbers are relatively prime.

The Attempt at a Solution

If they share common factors then it should divide their difference so I look at
n>x
[itex] (2^{2^n}+1)-(2^{2^x}+1)=2^{2^x}(2^{2^n-2^x}-1) [/itex]
Now since fermat numbers are odd their factors will have to be contained in
[itex] (2^{2^n-2^x}-1) [/itex] Now if they share common factors then it should divide
[itex] (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)[/itex]
Since fermat numbers are odd their factors must divide into
[itex] (2^{-2^x}+1) [/itex] but this is not an integer so this contradicts our assumption that it will divide our sum, so fermat numbers are relatively prime.

 

[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

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

 

[Joffan]

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

 

[Dick]

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

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.

 

[Curious3141]

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.

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