1
$\begingroup$

Assume $p$ is a prime and $a$ is some primitive root modulo $p$.

I have already shown that if gcd$(k, p-1)=1$ then $a^k$ is also a primitive root modulo $p$.

So what I'm wondering is how to extend this to prove that all primitive roots modulo $p$ are congruent to $a^k$ (for some $k$ such that gcd$(k, p-1)=1$)?

$\endgroup$
1
$\begingroup$

Since $a$ is a primitive root of $p$, any $x$ not divisible by $p$ is congruent to $a^k$ for some positive integer $k$. In particular, any candidate for primitive root must be of shape $a^k$ for some $k$.

we show that if $\gcd(k,p-1)\gt 1$, then $a^k$ is not a primitive root of $p$.

Let $d=\gcd(k,p-1)$, where $d\gt 1$. Let $k=k_1d$, Then $$(a^k)^{(p-1)/d}=a^{k_1(p-1)}=(a^{p-1})^{k_1}\equiv 1\pmod{p}$$ Thus $a^k$ has order $\le (p-1)/d$, and therefore cannot be a primitive root of $p$.

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