Let $p, q$ be distinct odd primes, I would like to compute the number of solution $\mod p$ to the congruence $x^q \equiv 1 \mod p$. (Show that it's $gcd(q, p – 1))$
If $x^q \equiv 1 \mod p$, since $q$ is prime, this must mean that $x$ is either $1$ or has order $q$. Hence, the problem reduces to finding the number of elements of $U_p$ which is either $1$ or has order $q$. If $ q \nmid p – 1$, then there is only one element, namely $1$. If $q \mid p – 1$, then the number of elements of order $q$ is $\phi(q) = q – 1$, and so the number of solutions to the congruence $\mod p$ is $q – 1 + 1 = q$, and in either case the number of solutions is $\gcd(q, p – 1)$.
Does this look fine?
Best Answer
The key to questions like this is that (1) the group of nonzero elements of $\mathbb Z/(p)$ is cyclic of order $p-1$; and (2) in a cyclic group of order $n$, there is just one subgroup of order $d$ for every divisor $d$ of $n$, and these are the only subgroups of the original cyclic group. Now you fill in the details.