# 2^2^n - 1 has at least n distinct prime factors

1. Jan 29, 2013

### stgermaine

1. The problem statement, all variables and given/known data[/b]
Prove that the number $2^{2^{n}} - 1$ has at least n distinct prime factors.

2. Relevant equations
Seems like I'd have to use Fermat numbers and its properties to solve this question.

$F(n) = 2^{2^{n}} + 1$
$F(n) = (F(n-1) - 1)^{2} + 1$
$F(n) = F(0)*F(1)*...*F(n-1) +2$

3. The attempt at a solution
I think that I should try to show the recurrence relationships to demonstrate how I arrived at the answer.

The third equation would be the most helpful, since I have to show that F(n) - 2 has n distinct prime factors. I know how to show that gcd(F(m), F(n)) = 1, m!=n.

I tried to derive the third equation from the second one.
$F(n) - 2 = (F(n-1) - 1)^{2} - 1 = [F(n-1)^{2} - 2*F(n-1) + 1] - 1 = F(n-1)(F(n-1)-2)$

I'd then substitute F(n-2)(F(n-2)-2) for F(n-1)-2 and try to work my way to the third equation given in section 2.

2. Jan 29, 2013

### Joffan

You can get your third equation directly by factoring your expression like $(x^2-1)$ repeatedly.

Last edited: Jan 29, 2013
3. Feb 7, 2013

### Joffan

In case you didn't understand this and are still puzzled,
$$(x^2-1) = (x-1)(x+1)$$
$$2^{2x}-1 = (2^x-1)(2^x+1)$$
$$2^{2^x}-1 = (2^{2^{x-1}}-1)(2^{2^{x-1}}+1)$$