Take the 2-minute tour ×
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.

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|improve this question
1  
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
add comment

3 Answers 3

up vote 7 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|improve this answer
add comment

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, applied it to Fermat's Last Theorem (first case) and related diophantine equations, e.g. see Ribenboim's book 13 Lectures on FLT, 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|improve this answer
add comment

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

share|improve this answer
add comment

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.