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

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

`n=1`.

ii) Inductive step:

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

`f(n+1)`.

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}`.