# 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$
-

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$.

-
You said "$p$ divides $2^n-1$, so $2^n \equiv 1 \pmod p$". How does this step work? –  Nayuki Minase Feb 27 '12 at 6:31
@Nayuki Minase: We say that $x\equiv y \pmod m$ if $m$ divides $x-y$. Take $x=2^n$, $y=1$, $m=p$. Since definitely $p$ divides $2^n-1$ (in fact is exactly equal to $2^n-1$), we have $2^n\equiv 1 \pmod p$. –  André Nicolas Feb 27 '12 at 6:38
Ohh right, I understand now. I guess I'm not comfortable enough with modular arithmetic that such an elementary fact slipped past me, heh. –  Nayuki Minase Feb 27 '12 at 6:40
Alternate explanation: $p$ divides $2^n-1$, so $2^n-1$ divided by $p$ leaves no remainder, thus $2^n-1 \equiv 0 \mod p$. –  Nayuki Minase Feb 27 '12 at 6:42
@Nayuki Minase: I can see why it is puzzling, in a sense it is *too simple. One expects to have to work a bit to show that a congruence holds. In this case, there was no real work involved. –  André Nicolas Feb 27 '12 at 6:44

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.

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$.

-

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).

-
Why are all your variables in uppercase? –  Nayuki Minase Mar 2 '12 at 5:05
@Nayuki It makes expressions in exponents easier to read. –  Bill Dubuque Mar 2 '12 at 5:25
Other than that, I'm sorry but I don't understand your argument at all. –  Nayuki Minase Mar 2 '12 at 6:34
@Nayuki Do you not understand the proof in the hint, or do you not understand how it applies to your case? –  Bill Dubuque Mar 3 '12 at 1:08
I didn't understand how your answer fits with my question. Please see the other answers as examples of proofs that I did understand. –  Nayuki Minase Mar 3 '12 at 23:33