9
$\begingroup$

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$

3 Answers 3

0

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

  • 0
    Why are all your variables in uppercase?2012-03-02
  • 0
    @Nayuki It makes expressions in exponents easier to read.2012-03-02
  • 0
    Other than that, I'm sorry but I don't understand your argument at all.2012-03-02
  • 0
    @Nayuki Do you not understand the proof in the hint, or do you not understand how it applies to your case?2012-03-03
  • 0
    I didn't understand how your answer fits with my question. Please see the other answers as examples of proofs that I did understand.2012-03-03
  • 0
    @Nayuki Alas, it is difficult for me to clarify my answer unless you can elaborate on what is not clear.2012-03-03
  • 0
    I am extremely uncomfortable with how much you left implied, such as the instantiation of $K$, the references to GCD, and the very non-obvious invocation of Fermat's little theorem for $K$. Only after rereading your proof a few times on separate days did I start to believe that it plausibly leads to an answer at all. -1.2012-03-03
  • 0
    @Nayuki There is no use of little Fermat, and the notation $(a,b)$ for the gcd is standard in number theory. No doubt it is a *very* concise proof, but that is by design, to highlight only what is *essential* (something I do frequently). As I said, you can find further details in the linked thread. I don't know what you mean by "instantiation of K".2012-03-03
  • 0
    I mean introduction of a new variable, whose role and meaning is unexplained.2012-03-03
  • 0
    @Nayuki It shows if $\rm\:A\ne 1\:$ and $\rm\:A^P = 1 = A^K,\:$ then $\rm\:P\:$ prime $\:\Rightarrow$ $\rm\:P\ |\ K,\:$ i.e. $\rm\:A\:$ has order $\rm\:P.$ $\quad\ \ $ In the proof $\rm\:K\:$ denotaes any natural, as should be clear.2012-03-03
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$.

  • 0
    You said "$p$ divides $2^n-1$, so $2^n \equiv 1 \pmod p$". How does this step work?2012-02-27
  • 0
    @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$.2012-02-27
  • 0
    Ohh right, I understand now. I guess I'm not comfortable enough with modular arithmetic that such an elementary fact slipped past me, heh.2012-02-27
  • 0
    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$.2012-02-27
  • 0
    @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.2012-02-27
  • 0
    To the alternate explanation: Yes, exactly.2012-02-27
0

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