# Homework Help: Proof about 2 numbers being relatively prime.

1. May 28, 2013

### cragar

1. The problem statement, all variables and given/known data
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.
3. 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 im 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.

2. May 28, 2013

### haruspex

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?

3. May 29, 2013

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

4. May 29, 2013

### haruspex

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

5. May 29, 2013

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

Last edited: May 29, 2013