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?