Divisibility of Mersenne numbers Is there a way to prove that $2$ is the only prime that never divides $2^n-1$ ? Obviously we can ignore all primes that are themselves of this form. Some other examples:
$$5\,|\,2^4-1 \qquad 9\,|\,2^6-1 \qquad 11\,|\,2^{10}-1 \qquad 13\,|\,2^{12}-1 \qquad 17\,|\,2^8-1$$
I checked for all $p<10^6$. Thanks in advance.

You have noted that
$$
3\mid 2^2-1,\quad
5\mid 2^4-1,\quad
7\mid 2^6-1,\quad
11\mid 2^{10}-1,\quad
13\mid 2^{12}-1,\quad
17\mid 2^8-1
$$
and the last one seems an outlier, but since $2^{16}-1=(2^8-1)(2^8+1)$, you still have that $17\mid2^{16}-1$.
Now do you see something? The exponent is the prime number minus $1$.
OK, the conjecture might be that $p\mid2^{p-1}-1$ when $p$ is an odd prime. Does this ring a bell? What about any $a$ with $0<a<p$? Oh, yes, it holds that
$$
a^{p-1}-1\equiv 0\pmod{p}
$$
by Euler's theorem: if $\gcd(a,n)=1$, then $a^{\varphi(n)}\equiv1\pmod{n}$, where $\varphi$ is the totient function. For $p$ a prime, $\varphi(p)=p-1$.
