Prove that if $2^n-1$ is prime, then $n$ divides $2^n-2$ Suppose $p = 2^n - 1$ is prime. Show that $n \: | \: 2^n - 2$, or equivalently $n \: | \: p - 1$.
With hint: The order of any element in this field divides $p-1$.
Example: $n=7, \; p=127 \:\Rightarrow\: 7 \: | \: 126$.

I don't have any progress that seems to lead to a proof, but here are some of my ideas:


*

*Because $p$ is a Mersenne prime, $n$ must be prime

*Use Fermat's little theorem

*Show that $2^n - 2 \equiv 0 \mod n$

 A: You have mentioned ingredients that lead to a proof. As you point out, the number $n$ must be prime, so we can use Fermat's Theorem.
There are a couple of different versions of Fermat's Theorem. Each version is not difficult to derive from the other.
Version 1: If $n$ is prime, then for any integer $a$, we have $a^n \equiv a \pmod n$.  This says directly that $n$ divides $a^n-a$, which is exactly what you want to show, in the special case $a=2$.
Version 2: If $n$ is prime, and $n$ does not divide $a$, then $a^{n-1} \equiv 1 \pmod n$. 
In your case, $n$ is odd, so if $a=2$, then $n$ does not divide $a$. It follows that $n$ divides $2^{n-1}-1$, and therefore $n$ divides twice this number, which is $2^n-2$. 
However, you were given a hint which enables us to bypass Fermat's Theorem. So probably you were expected to argue as follows. 
Since $p=2^n-1$, certainly $p$ divides  $2^n-1$, so $2^n \equiv 1 \pmod p$.  That implies that the order of $2$ in the field $\mathbb{Z}_p$ is a divisor of $n$. But the order of $2$ is exactly $n$, since $n$ is prime, and therefore the only divisors of $n$ are $1$ and $n$. 
The order of any element of the field $\mathbb{Z}_p$ divides $p-1$. Since the order of $2$ in this field is $n$, we conclude that $n$ divides $p-1$, that is, $n$ divides $2^n-2$.  
A: Simpler answer:
Let $n \in \mathbb{N}^+$ be arbitrary. Let $p = 2^n-1$.
Clearly, $2^n \equiv 1 \mod {2^n-1}$. Moveover, $n$ is the smallest power where $2^n \equiv 1$. Thus the order of 2 in $\mathbb{Z}_{p}$ is $n$.
Now if $p$ is prime, then Fermat's little theorem guarantees that for any $a$ (except 0), $a^{p-1} \equiv 1 \mod p$. Furthermore, the order of $a$ divides $p-1$.
$a=2$ has order $n$, therefore $n$ divides $p-1 = 2^n - 2$, as wanted.

Complicated answer:
Fact: $x^{ab} - 1 = (x^a - 1)(x^{(b-1)a} + \ldots + x^{3a} + x^{2a} + x^a + 1)$. So for the special case of $2^n-1$, if $n$ is composite then $2^n-1$ can be factored. By contrapositive, if $2^n-1$ is prime then $n$ is prime.
Fermat's little theorem: If $q$ is prime, then $\forall a \in \mathbb{Z}, \; a^q \equiv a \mod q$.
Now, $n \: | \: 2^n - 2$ is equivalent to saying that $2^n-2$ is a multiple of $n$, or $2^n-2 \equiv 0 \mod n$.
We established that $n$ must be prime. By applying FLT with $a=2$, we get $2^n \equiv 2 \mod n$, which is easily equivalent to $2^n - 2 \equiv 0 \mod n$.
A: Hint $\rm\: prime\: P,\: A^P\!\! = 1 = A^K\!\Rightarrow A^{(P,\:K)}\!\!=1,$  so $\rm\: P| K\ $  [if $\rm (P,K) = P$]$\:$ or $\rm\: A\! =\! 1\:$ [if $\rm (P,K) = 1$]
For further detail see this question: If the order divides a prime P then the order is P (or 1).
