Proof about 2 numbers being relatively prime.

[cragar]

Homework Statement

Prove that their are an infinite amount of primes by observing that in the series
$2^2+1, 2^{2^2}+1,2^{2^3}+1,2^{2^4}+1,...$
every 2 numbers are relatively prime.

The Attempt at a Solution

I was going to take 2 of the numbers in the series and look at their difference because if they have common factors then it should divide their difference, but then I am not sure how this will work.
or maybe I should look at these numbers mod2 or something, well I guess mod2 these all equal 1.

 

[haruspex]

I was going to take 2 of the numbers in the series and look at their difference

Seems a good start. Suppose p divides each, so it divide the difference. Can you then discard a factor of the difference and deduce that p divides the remaining factor?

 

[cragar]

If I look at $2^4+1-(2^2+1)=2^4-2^2=2^2(2^2-1)$ we know that
$2^2+1$ and $2^2-1$ are relatively prime because they are an odd number separated by a power of 2. But then I was trying to generalize this proof. where we have
$2^x+1,2^y+1$ x<y then $2^y+1-2^x-1=2^x(2^{y-x}-1$ I guess I could make a similar argument that $2^{y-x}-1$ and $2^x+1$ are relatively prime.

 

[haruspex]

$2^y+1-2^x-1=2^x(2^{y-x}-1$ I guess I could make a similar argument that $2^{y-x}-1$ and $2^x+1$ are relatively prime.

I don't think that argument will work.
As I said, suppose p divides 2^2x+1 and 2^2y+1, so it follows that p divides 2^2y-2x-1. Can you now construct more numbers it must divide?

 

[Dick]

These numbers are called Fermat numbers. Define F(n)=2^(2^n)+1. Then if you can show the recursion relation F(n)=F(n-1)F(n-2)...F(1)F(0)+2, you are pretty much home free. Try concentrating on proving that. That's the usual route. Start by writing down the most obvious relation between F(n) and F(n-1) that you can think of.