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.

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$
share|improve this question

3 Answers 3

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

share|improve this answer
    
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
up vote 0 down vote accepted

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

share|improve this answer

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

share|improve this answer
    
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

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.