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

Question

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?

Answer 1

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?

Answer 2

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.