# Given 2 is primitive root (mod p), showing that every non-zero element of Z(p) is expressable as power of [2] (mod p)

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?

• 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? – Jyrki Lahtonen Jan 8 at 5:34
• Also, please check our guide to new askers for tips in making your question passable. – Jyrki Lahtonen Jan 8 at 5:35
• "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? – Blackb3ard Jan 8 at 7:01
• So there is nothing to prove :-) – Jyrki Lahtonen Jan 8 at 8:07
• How about I change the word "prove" to "show" or "verify". Does this better describe my question to you? – 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.