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?

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
7
  • 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
    Commented Mar 10, 2015 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
    Commented Mar 10, 2015 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
    Commented Mar 10, 2015 at 18:48
  • $\begingroup$ Ah, no, sorry, I was being silly. $\endgroup$
    – Qiaochu Yuan
    Commented Mar 10, 2015 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
    Commented Mar 10, 2015 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.

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Fermat's little theorem? (sorry, I'm not a mathematician, so my comprehension + acceptance comes fairly slowly) $\endgroup$
    – Jason S
    Commented Mar 10, 2015 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
    Commented Mar 10, 2015 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
    Commented Mar 10, 2015 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
    Commented Mar 10, 2015 at 22:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .