Divisors of $2^{2^{127}-1}-1$

Question

Consider the recursively defined number sequence

$f(0) = 2$
$f(n+1) = 2^{f(n)}-1$

This sequence goes like $2$, $3$, $7$, $127$, $2^{127}-1$, $2^{2^{127}-1}-1$, $\ldots$.

Facts:

• $2$, $3$, $7$, $127$, $2^{127}-1$ all are prime numbers.
• It is not known whether $2^{2^{127}-1}-1$ is prime.
  (That number is way bigger than the largest prime that has been found so far.)

Puzzle: Show that $f(5)=2^{2^{127}-1}-1$ has no divisors below $f(4)=2^{127}-1$.

Answer 1

Let $p=2^{127}-1$, and $q$ be a prime factor of $2^p-1$.

We know from Fermat's little theorem that q is a factor of $2^{q-1}-1$. If a prime divides $2^a-1$ and $2^b-1$, it divides $2^{ma}-1$ and $2^{nb}-1$, implying that it divides $2^{|ma-nb|}-1$. That is, it divides $2^{\gcd(a,b)}-1$.

Thus we have q divides $2^{\gcd(p,q-1)}-1$. Since $p$ is prime and $q>1$, we obtain that $p=\gcd(p,q-1)\implies q=kp+1\implies q>p$

Answer 2

The solution I had myself is this.

For the sake of contradiction, let me have a prime number $p < 2^{127}-1$ that divides $2^{2^{127}-1}-1$. Then we need to have $2^{2^{127}-1} mod(p) = 1$, where x mod(p) is the remainder after dividing x by p.

Now, consider the sequence $g(n) = 2^{n} mod(p)$. We have g(0) = 1, the saught remainder. Since $g$ is a repeating sequence and $p$ is prime, the next n for which g(n)=1, is smaller than or equal to $p$ and thus smaller than $2^{127}-1$. Let's call that n c. So, we have g(c) = 1.

But now, only for natural numbers $a$, we have $g(ac) = 1$. But we need to have $g(2^{127}-1) = 1$, where $2^{127}-1$ is prime. $ac=2^{127}-1$ is a contradiction.