Number of elements of $\mathbb{Z}_p$ that satisfy a certain property

Question

Let $S(n,p)=\{a\in \mathbb{Z}_p : a^n=1$ (mod $p$)$\}$ where $p\geq3$ is a prime number and $1\leq n\leq p$. I am interested in finding a general formula for cardinality of $S(n,p)$. For example, I know that $|S(1,p)|=1$ and $|S(p-1,p)|=p-1$ (by Fermat's little theorem).

Answer 1

We know that $\mathbb{Z}_p^\times = \{ 1,2,\dots,p-1 \}$ form a group under multiplication modulo $p$. Since $p$ is prime, this group is cyclic.

In a cyclic group of order $n$, the number of elements of order $k$ is $\varphi(k)$ if $k$ divides $n$ (and 0 otherwise) where $\varphi(k)$ is Euler's Totient Function.

Next, $x^n \equiv 1$ (mod $p$) iff the order of $x$ in $\mathbb{Z}_p^\times$ is divisible by $n$. So $|S(n,p)|$ is the number of elements of orders dividing $n$ in $\mathbb{Z}_p^\times$.

This means that $$|S(n,p)| = \sum \varphi(k)$$ where the sum is over all $k$ that divide both $n$ and $p-1$ (the order of $\mathbb{Z}_p^\times = \{ 1,2,\dots,p-1 \}$). This means that $k$ ranges over the divisors of $\mathrm{gcd}(n,p-1)$.

Finally, a theorem of Gauss states that $\sum\limits_{d \mbox{ divides } \ell} \varphi(d)=\ell$.

Therefore, $|S(n,p)|=\mathrm{gcd}(n,p-1)$.

Answer 2

Already this has been answered. But I'd like to make two points: as $0$ is ruled out we are looking at a subset of the group $\mathbf{Z}_p^*$. And $x\mapsto x^n$ is a homomorphism of this group, and so the solution set $S(n,p)$ you are looking for is the kernel of that homomorphism.