Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The $n$-th Mersenne number $M_n$ is defined as $$M_n=2^n-1$$ A great deal of research focuses on Mersenne primes. What is known in the opposite direction about Mersenne numbers with only small factors (i.e. smooth numbers)? In particular, if we let $P_n$ denote the largest prime factor of $M_n$, are any results known of the form $$\liminf_{n\rightarrow \infty}\frac{P_n}{f(n)}= 1$$ for some function $f$?

I've only come across two (fairly distant) bounds so far. If we consider even-valued $n$, then $M_n=M_{n/2}(M_{n/2}+2)$, so: $$\liminf_{n\rightarrow \infty}\frac{P_n}{2^{n/2}}\leq 1$$ In the other direction, [1] shows that $P_n\geq 2n+1$ for $n>12$, so $$\liminf_{n\rightarrow \infty}\frac{P_n}{2n}\geq 1$$

[1] A. Schinzel, On primitive prime factors of $a^n-b^n$, Proc. Cambridge Philos. Soc. 58 (1962), 555-562.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

I can give you a slightly better upper bound. Recall that $2^n - 1 = \prod_{d | n} \Phi_d(2)$ where $\Phi_d$ is a cyclotomic polynomial. Now,

$$\Phi_d(2) = \prod_{(k, d) = 1} (2 - \zeta_d^k) \le 3^{\varphi(d)}$$

so that in particular the largest prime factor of $2^n - 1$ is at most $3^{\varphi(n)}$. By taking $n$ to be a product of the first $k$ primes and letting $k$ tend to infinity we have $\liminf_{n \to \infty} \frac{\varphi(n)}{n} = 0$, hence

$$\liminf_{n \to \infty} \frac{P_n}{c^n} = 0$$

for any $c > 1$. In fact if $n$ is the product of the first $k$ primes then we should expect something like $3^{\varphi(n)} \approx 3^{ \frac{n}{\log k} }$ but this doesn't seem like a big improvement to me.

share|improve this answer

I guess lower bounds on the largest prime factor of Mersenne numbers are not only interesting in number theory but also in coding theory (see this article of K. Kedlaya and S. Yekhanin here). They say the current strongest lower bound is $$P_n>\epsilon(n)n\log^2(n)/\log\log(n)$$ for all $n$ except for a set of asymptotic density zero and all functions $\epsilon$ that tend to zero monotonically and arbitraily slowly, and is due to C. Stewart. See his articles "The greatest prime factor of $a^n-b^n$" and "On divisors of Fermat, Fibonacci, Lucas, and Lehmer numbers".

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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