For any $n$, is there a prime factor of $2^n-1$ which is not a factor of $2^m-1$ for $m < n$? 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?
 A: 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 first 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.
A: No. $2^6-1 = 3^2 \cdot 7$. But we have that $3|2^2-1$ and $7|2^3-1$
A: 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).
