Number of solutions to $x^n \equiv 1 \mod p$

Solution 1:

A zest of group theory could dispense us of any calculation : $\mathbf F_p =\mathbf Z/p\mathbf Z$ is a field because $p$ is prime, and its multiplicative group ${\mathbf F_p}^*$ is cyclic of order $p-1$. A characteristic property of a cyclic group $C_m$ of order $m$ is that for any $d\mid m$, $C_m$ admits a unique subgroup (necessarily cyclic) of order $d$. The solutions of $x^n\equiv 1$ mod $p$ form a subgroup $S$ of ${\mathbf F_p}^*$ whose order must be a common divisor of $n$ and $p-1$. If $D =gcd(n, p-1)$, the existence and uniqueness property above ensures that $S$ has order $D$.

Solution 2:

Following Yuan's hint you can use primitive roots to solve the question. As $p$ is prime such a primitive root $g$ exists, which means that for every $1 \le k \le p-1$ there exists $n_0$ s.t. $g^{n_0} \equiv k \pmod p$

Now note that the equation $x^n \equiv 1 \pmod p$ has only the trivial solution when $\gcd(n,p-1) = 1$, as then we have that $\text{ord}_p(x) |n$ and $\text{ord}_p(x) \mid p-1$ by Fermat's Little Theorem, so $\text{ord}_p(x) \mid \gcd(n,p-1) = 1$, so we must have $\text{ord}_p(x) = 1$, i.e. $x \equiv 1 \pmod{p}$

Now let $\gcd(n,p-1) = d \not = 1$. Now assume that $g^k$ is a solution. Then we have that: $1 \equiv g^{kn}$, but the order of $g$ is $p-1$, so we must have $p-1 \mid kn$, i.e. $\frac{p-1}{d} \mid k$, so $k= m \cdot\frac{p-1}{d}$. From this we can conclude that the solution of equations are the numbers $1, g^{\frac{p-1}{d}}, g^{2\cdot\frac{p-1}{d}}, \dots ,g^{(d-1)\frac{p-1}{d}}$. So therefore we get that there are at exactly $d = \gcd(n,p-1)$ solutions. of $x^n \equiv 1 \pmod p$