1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 2^2^n - 1 has at least n distinct prime factors

  1. Jan 29, 2013 #1
    1. The problem statement, all variables and given/known data[/b]
    Prove that the number [itex]2^{2^{n}} - 1[/itex] 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.

    [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]

    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.
    [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
  2. jcsd
  3. Jan 29, 2013 #2
    You can get your third equation directly by factoring your expression like ##(x^2-1)## repeatedly.
    Last edited: Jan 29, 2013
  4. Feb 7, 2013 #3
    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)$$
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook