4
$\begingroup$

I've checked the factorization of $2^N - 1$ up through N = 120 for the largest prime factor, and it looks like the largest value of N where $2^N-1$ has a largest prime factor under 2500 is N = 60 (largest prime factor = 1321). As N gets larger, the largest prime factors get larger, even for the "abundant" numbers like 96, 108, and 120.

Is there a way to prove that no value of N > 60 exists such that the largest prime factor of $2^N - 1$ is less than 2500?

$\endgroup$
13
$\begingroup$

Zsigmondy's theorem implies that when $n \ge 7$, $2^n - 1$ has a prime divisor not dividing $2^k - 1$ for any $k < n$. So pick $n_0$ large enough that every prime number less than $2500$ divides $2^k - 1$ for some $k \le n_0$, then take $n > n_0$. This proves the desired claim for sufficiently large $n$ and then it suffices to check finitely many cases.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Note also that $2^n - 1$ has a factorization into factors $\prod_{d | n} \Phi_d(2)$, where $\Phi_d$ is the $d^{th}$ cyclotomic polynomial (en.wikipedia.org/wiki/Cyclotomic_polynomial). So all of the interesting new factors in $2^n - 1$ come from its factor $\Phi_n(2)$. $\endgroup$ – Qiaochu Yuan Mar 10 '15 at 18:17
  • $\begingroup$ It appears that $n_0 = 2476$ ($2477 | 2^{2476}-1$, and 2477 is the largest prime < 2500)... looks like I've got a lot of checking to do. :-) $\endgroup$ – Jason S Mar 10 '15 at 18:41
  • $\begingroup$ ?? I just ran through all of the prime numbers less than 2500, and they all divide $2^k - 1$ for some k <= 2476. Did I misread? $\endgroup$ – Jason S Mar 10 '15 at 18:48
  • $\begingroup$ Ah, no, sorry, I was being silly. $\endgroup$ – Qiaochu Yuan Mar 10 '15 at 18:48
  • 4
    $\begingroup$ In other words (restated for nonmathematicians like me): Zsigmondy's / Bang's theorems say that for each new $n \geq 7$, $2^n-1$ picks up a new prime factor not present in any $2^k-1$ for $k<n$. All the prime numbers less than 2500 show up as factors of $2^k-1$ for some $k \leq 2476$. So any value of $n > 2476$ must have a prime factor greater than 2500. Checking the values $2^n-1$ for all $n \leq 2476$, and factoring out primes < 2500, the only values of n where $2^n-1$ factors into primes under 2500 are $2\leq n\leq 12$ and 14, 15, 16, 18, 20, 21, 22, 24, 25, 28, 29, 30, 36, 44, 48, 60. $\endgroup$ – Jason S Mar 10 '15 at 19:14
19
$\begingroup$

A recent breakthrough on this problem is the work of Cam Stewart (the paper has appeared in Acta Mathematica). Proving a conjecture of Erdos, Stewart shows that the largest prime factor of $2^n-1$ is at least $$ n \exp\Big( \frac{\log n}{104 \log \log n}\Big), $$ if $n$ is large enough. He also gives many related earlier results: for example a result of Schinzel which shows that the largest prime factor of $2^n-1$ is at least $2n+1$ for $n\ge 13$, and discusses other work conditional on GRH or abc.

| cite | improve this answer | |
$\endgroup$
8
$\begingroup$

It is true that if $N > 60$, then $2^{N} - 1$ has a prime factor $> 2500$.

Here's another approach. First, observe that every prime factor of $2^{p} - 1$ is $\equiv 1 \pmod{p}$. Combining this with the observation that if $a | b$, then $2^{a} - 1 | 2^{b} - 1$, we see that if $2^{N} - 1$ has all prime factors $\leq 2500$, then all prime factors of $N$ are $< 2500$. Checking these primes, we see that $2^{p} - 1$ has a prime factor $> 2500$ unless $p = 2, 3, 5, 7, 11$ or $29$. Hence if all the prime factors of $2^{N} - 1$ are less than $2500$, then all prime divisors of $N$ are in the set $S = \{ 2, 3, 5, 7, 11, 29 \}$.

We find that $65537$ is a prime factor of $2^{32} - 1$ and this means that $N$ cannot be a multiple of $32$ if $2^{N} - 1$ has all prime divisors $< 2500$. Similar arguments show that $N$ cannot be a multiple of $3^{3}$, $5^{3}$, $7^{3}$, $11^{2}$ or $29^{2}$. This implies that $N$ divides $56271600$, and checking all such divisors, we see that $N = 60$ is the largest possible.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Fermat's little theorem? (sorry, I'm not a mathematician, so my comprehension + acceptance comes fairly slowly) $\endgroup$ – Jason S Mar 10 '15 at 18:45
  • 2
    $\begingroup$ @Jason: not quite. Fermat's little theorem only tells you that $2^p - 1 \equiv 1 \bmod p$. Jeremy is using a stronger fact: if $q$ is any prime such that $2^p \equiv 1 \bmod q$, then $q \equiv 1 \bmod p$. The reason is that the hypothesis means that $2$ is an element of order $p$ in the group of units $\bmod q$, which has size $q - 1$, and so by Lagrange's theorem $p$ must divide $q - 1$. $\endgroup$ – Qiaochu Yuan Mar 10 '15 at 18:48
  • $\begingroup$ hmm... Jeremy: any chance you could follow up with smaller conceptual chunks? I'm afraid I lost you. :-( $\endgroup$ – Jason S Mar 10 '15 at 18:55
  • $\begingroup$ I've edited my answer to fill in a bit more details. I hope it's easier to follow now. If you have questions about a particular point, let me know. $\endgroup$ – Jeremy Rouse Mar 10 '15 at 22:07

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.