0
$\begingroup$

Prove that for the primitive root $[g]$ modulo $p$ we have $[g]^m=[g]^n \iff p-1\mid m-n$.

Proof: We know

If $g$ is a primitive $p$-root of unity, then $g^n\equiv 1 \pmod p \iff (p-1)\mid n$. Hence if $n$ is not divisible by $(p-1)$ we have $s_n(p)\equiv 0 \pmod p$. Similarly, If $g$ is a primitive $p$-root of unity, then $g^m\equiv 1 \pmod p \iff (p-1)\mid m$. Hence if $m$ is not divisible by $(p-1)$ we have $s_m(p)\equiv 0 \pmod p$.

Can I use these statements to prove the statement above?

$\endgroup$
  • 2
    $\begingroup$ $g^m \equiv g^n \iff g^{m-n} \equiv 1 \pmod{p}$ Since the order of $g$ is $p-1$, therefore $p-1$ divides $m-n$. $\endgroup$ – Anurag A Jun 16 '14 at 4:38
1
$\begingroup$

We have $g^m = g^n$, so multiply through by $(g^n)^{-1} = g^{-n}$:

$$g^{m-n} \equiv 1 \pmod{p}$$

Since $g$ is a generator of the multiplicative group $\mathbb{Z}_p^\times$, then the above holds $\iff$ $m-n$ is a multiple of $|g| = |\mathbb{Z}_p^\times|= p-1$.

$\endgroup$
0
$\begingroup$

Hint: $\mathbb{Z}_p^{\times}$ is a group and the order of $g$ is $p-1$

$\endgroup$

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.