Prove that  `2^(2^n)-1` has `n` different prime factors, where `n in {NN: n>0}`.  

1 Answer | Add Yours

mathsworkmusic's profile pic

mathsworkmusic | (Level 2) Educator

Posted on

Prove that `f(n) = 2^(2^n) - 1`  has `n` different primes, `n in {NN: n>0}` 

We use Proof by Induction.

i) Base case` `:

   Does the result hold for `f(1)`? 

   If  `n=1`,  `2^(2^n)-1 = 3`

   This has precisely `n=1` prime factors so the expression is true for


ii) Inductive step:

    Here we show that if the result holds for `f(n)` then it also holds for


    We have that

    `2^(2^(n+1)) - 1 = (2^(2^n)-1)(2^(2^n)+1)`

    If the result holds for `f(n)` then the first term on the r.h.s has `n` different

    prime factors. The second of the terms on the r.h.s is a Fermat number

    and so is also a prime factor. It is larger than `2^(2^n)-1` so it must be larger

    than all the prime factors of `f(n)`. Therefore it is different to these `n`

    prime factors.

    Therefore if `f(n)` has `n` different prime factors that implies that

   `f(n+1)` has   `n+1`  different prime factors.


Since the result holds for `f(1)` (the base case) and we have shown that if `f(n)` holds (for any `n`) then `f(n+1)` also holds.

Thus, by induction we have shown that `f(n)` holds for all `n` where `n in {NN: n>0}`.





We’ve answered 317,685 questions. We can answer yours, too.

Ask a question