0
$\begingroup$

Prove that exactly $\varphi (d)$ residues have order $d$ modulo $p$ for all $d \mid \varphi(p)$ where $p$ is prime.

I was wondering if there was a way to solve this using number theory and not group theory. Here was the start of my attempt:

Let $g$ be a primitive root modulo $p$, so that $\text{ord}_p(g) = \varphi(p) = p-1$ and $\{g,g^2,\ldots,g^{p-1}\}$ is the complete residue system modulo $p$. It suffices to find the number of $m$ such that $\text{ord}_p(g^m) = d$.

We know that $g^{dm} = g^{(p-1) \cdot \frac{dm}{p-1}}$.

How do we continue from here?

$\endgroup$

1 Answer 1

2
$\begingroup$

If $d \mid \phi(p)$ then write $d'$ for the number such that $dd' = \phi(p)$. Now $h = g^{d'}$ has order $d$ (if $h^k = 1$ for $k<d $ then $g^{d'k} = 1$ with $d'k < \phi(p)$ and $g$ isn't a primitive root). We have that $h^m$ also has order $d \iff \gcd(m,d)=1$. We now have $\phi(d)$ elements of order $d$. These are the only ones: Let $g^k$ be of order $d$ then $g^{kd} = 1$ thus $\phi(p)=d'd\mid kd$, so $d'|k$ and $g^k$ is a power of $h$ of order $d$.

$\endgroup$
0

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.