- #1

stgermaine

- 48

- 0

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