Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is it guaranteed that there will be some $p$ such that $p\mid2^n-1$ but $p\nmid 2^m-1$ for any $m<n$?

In other words, does each $2^x-1$ introduce a new prime factor?

share|cite|improve this question
These are fairly famous and well studied: p is called a primitive divisor of the Mersenne number 2^n-1. Zsigmondy's theorem shows that they nearly always exist, which is very helpful in finite group theory. – Jack Schmidt Aug 12 '10 at 16:22
up vote 13 down vote accepted

Yes, it's true (except for $2^6-1=7\times 9$).

This is known as Bang's theorem, and is a corollary of Zsigmondy's Theorem.

You can find a proof here (Theorem 3).

share|cite|improve this answer

This result is due to Zsigmondy (1892), with special cases $(b=1)$ (re)discovered by Bang (1886), Birkhoff & Vandiver (1904) ... see Ribenboim, The New Book of Prime Number Records, p. 43, 67-68, 338, 437. Vandiver, a prolific researcher on FLT = Fermat's Last Theorem, applied it to the irst case of FLT and related diophantine equations, e.g. see Ribenboim's book 13 Lectures on Fermat's Last Theorem, pages 52,161,206,234,236.

Such results have many applications: a MathSciNet search on Anywhere=(Zsigmondy or (Birkhoff and Vandiver)) will find over 35 related Math Reviews. Schinzel (1974, MR 93k:11107) extended the theorem to arbitrary algebraic number fields $K$:

If $a$ and $b$ are algebraic integers in $K,\,$ $(a,b)=1,\,$ and $a/b$ is of degree $d$ and not a root of unity, then there exists $\,n_0 = n_0(d)\,$ such that for all $n > n_0,\,\ a^n - b^n\, $ has a prime ideal factor $P$ not dividing $\,a^m - b^m\, $ for all $ m < n$.

Later (1993, same MR) "he generalized this to show that every algebraic number which is not a root of unity satisfies only a finite number of independent generalized cyclotomic equations considered by the reviewer [in Structural properties of polylogarithms, Chapter 11, see p. 236, Amer. Math. Soc., Providence, RI, 1991; see MR 93b:11158]".

There are also elliptic and polynomial generalizations.

share|cite|improve this answer

No. $2^6-1 = 3^2 \cdot 7$. But we have that $3|2^2-1$ and $7|2^3-1$

share|cite|improve this answer

Your Answer


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.