# Proof: $2^{2^t}-1$ is divisible by at least $t$ distinct primes

A question into the elementary number theory. Proof: $2^{2^{t}}-1$ is divisible by at least $t$ distinct primes.

My ideas about the issue are the following:

Distinct primes, call them: $p_{1};p_{2};...;p_{k}$, we want to show that $k>t$ or $k=t$

So: $2^{2^{t}}=1$ (mod $p_{i}$) for all $1<i<k$ which perhaps could be solved by the Chinese remainder theorem. (and $i=1$, $i=k$)

And we know that $2^t\ |\ \phi(p_{i})=p_{i}-1$ so $2^t=1$ mod($p_{i}$) for all $1<i<k$ and $i=1$; $i=k$.

These are just observations, without a proof-strategy. Can anybody give me some direction? Thanx in advance!

• Can you show that changing $t$ to $t+1$ Increases the number of distinct prime divisors? – Aaron Meyerowitz Sep 25 '14 at 15:58

## 2 Answers

Hint

We have the following: $$2^{2^t}-1= (2^{2^{t-1}}-1)(2^{2^{t-1}}+1)$$ for $t\geq 1$.

• Okay, so we can write $2^{2^{t-1}}-1$ again as $(2^{2^{t-2}}-1)(2^{2^{t-2}}+1)$. And so on...? – iJup Sep 26 '14 at 11:00

Meanwhile, the question has been solved.

You can split up:

$(2^{2^{t}}-1)$

$=(2^{2^{t-1}}-1)(2^{2^{t-1}}+1)$

$=(2^{2^{t-1}}+1)(2^{2^{t-2}}-1)(2^{2^{t-2}}+1)=...=(2^{2^{t-1}}+1)(2^{2^{t-2}}+1)\cdot{}...\cdot{}(2^{2^{t-t}}+1)\cdot(2^{2^{t-t}}-1)$

The latter factor becomes 1. So $(2^{2^{t}}-1)$ gives us a product of $t$-different brackets. Now we want to show that $(2^{2^{t}}-1)$ brings $t$ different prime numbers. So we have tot investigate if $(2^{2^{t-i}}-1)$ is prime for all $1<i<t$ and $i=1,i=t$.

Using induction:

•$t=1$: $(2^{2^{1}}-1)=3$, there are $t=1$ different prime numbers. Correct.

Supose it is true for $t=k$, there are $t=k$ different prime numbers.

•$(2^{2^{k}}-1)$ brings $t=k$ different a prime numbers.

Investigate how many prime numbers $(2^{2^{t}}-1)$ produces for $t=k+1$.

•Since the $gcd((2^{2^{t}}-1);(2^{2^{t}}+1)=1,2$ and it could not be 2 because $(2^{2^{t}}-1)$ is odd it follows that the $gcd$ is one. An so brings a new prime number.

So $(2^{2^{t}}-1)$ is divisible by at least $t$ different prime numbers. :-)