Number of solution of exponential equation modulo p (prime)

Question

I have to find the number of solution of this congruential equation $x^k\equiv 1 (mod\space p)$. Surely I know that $x^{p-1}\equiv 1 (mod\space p)$ so, $x^d \equiv 1$ where $d$ is the MCD between $(p-1,k)$. Now I have to count how many divisor of $d$ there are, but I don't know how.

Answer 1

Let $g$ be a generator of $\mathbb{Z}_p$, then we can write $x=g^a$ for some positive integer $a$.

$x^k\equiv_p 1$ has atleast one solution ($x\equiv_p 1$), so $g^{ak}\equiv_p 1$. Since $g$ is a generator the smallest power, for which it equlals $1$ is $p-1$. This means that $p-1\mid ak$. We can therefore write $ak=(p-1)m$ for some positive integer $m$.

We want to find all the possible values of $a$, because then we know what the solutions, $g^a$, looks like. We have that $$a=\frac{(p-1)m}{k}$$ Let $d=\gcd(p-1,k)$ and $k=dk'$. Then we can write this as $$a=\frac{(p-1)m}{dk'}$$ where $\gcd(p-1,k')=1$. This means that $k'\mid m$, so let $m=k'm'$. We then finally get $$a=\frac{(p-1)m'}{d}$$ this tell us that $m'\in\{1,2,\dots, d\}$. So there are exactly $d=\gcd(p-1,k)$ solutions.