I'm trying to find out how I would go about showing this:

Given a prime number p >= 2, suppose 2 is a primitive root modulo p. Show that every non-zero element of Z(p) can be written as a power of [2] (mod p).

Z(p) refers to the congruence class modulo p.

Any ideas?

  • 2
    $\begingroup$ Isn't it the definition of a primitive root that all the residue classes are its powers? What is your definition of a primitive root? $\endgroup$ – Jyrki Lahtonen Jan 8 at 5:34
  • $\begingroup$ Also, please check our guide to new askers for tips in making your question passable. $\endgroup$ – Jyrki Lahtonen Jan 8 at 5:35
  • $\begingroup$ "Isn't it the definition of a primitive root that all the residue classes are its powers?" Yes, I think so too. Does it matter? $\endgroup$ – Blackb3ard Jan 8 at 7:01
  • $\begingroup$ So there is nothing to prove :-) $\endgroup$ – Jyrki Lahtonen Jan 8 at 8:07
  • $\begingroup$ How about I change the word "prove" to "show" or "verify". Does this better describe my question to you? $\endgroup$ – Blackb3ard Jan 8 at 8:59

Here's a sketch:

In the case $p=2$ the proof is immediate (check), so let $p>2$.

Suppose $2$ is a primitive root mod $p$. By definition, this means that $[2]^{p-1} \equiv 1$ mod $p$ and this is the smallest power of $2$ for which this happens.

Claim: $2^a$ with $a=1,\dots, p-1$ are $p-1$ distinct numbers mod $p$.

Proof: suppose not. Then...

Finally, if the numbers $2^a$ are all distinct mod $p$, then what does this mean?


I'm not sure it needs "proof" so much as a good "argument".

$2$ being a primitive root means that $2^{p-1} \equiv 1\pmod p$ but for all $k; 1\le k < p-1$ we do not have $2^{k}\equiv 1 \pmod p$.

The $2^k;1\le k \le p-1$ are distinct $\mod p$.

(Why? Because if $1\le a \le b \le p-1$ are such that $2^a \equiv 2^b \pmod p$ then $2^{a+(p-1)-b} \equiv 2^{b+(p-1)-b} = 2^{p-1} \equiv 1 \pmod p$. As $2$ is a primitive root this is impossible if $a+(p-1)-b < p-1$. So $a+(p-1) -b = p-1$ and $a = b$.)

And obviously no $2^k \equiv 0 \pmod p$. (Because $p\not\mid 2^k$).

(Oh... unless $p = 2$. But $2$ can not be a primitive root $\mod 2$. $2^k \equiv 1 \pmod 2$ is impossible.)

So the $2^k; 1\le k \le p-1$ are $p-1$ distinct non-zero residue classes.... as are the $p-1$ non-zero elements of $\mathbb Z_p$. So each non-zero element of $\mathbb Z_p$ is equivalent to one power of $2$ (and vice versa).

That's all.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.