1
$\begingroup$

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!

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

Hint

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

$\endgroup$
  • $\begingroup$ 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...? $\endgroup$ – iJup Sep 26 '14 at 11:00
3
$\begingroup$

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. :-)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.