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

[stgermaine]

1. Homework Statement [/b]
Prove that the number [itex]2^{2^{n}} - 1[/itex] has at least n distinct prime factors.

Homework Equations

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

[itex]F(n) = 2^{2^{n}} + 1[/itex]
[itex]F(n) = (F(n-1) - 1)^{2} + 1[/itex]
[itex]F(n) = F(0)*F(1)*...*F(n-1) +2[/itex]

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.
[itex]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)[/itex]

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.

Thank you for your help

 

[Joffan]

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

 

[Joffan]

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

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)$$