6
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Yes, it sounds fine, given you have already done the theorems implicitly quoted. A fairly simple argument using a primitive root of $p$ (generator of the multiplicative group) proves the same result for $x^k\equiv 1\pmod{p}$, where $k$ is not necessarily prime. $\endgroup$ – André Nicolas Mar 5 '13 at 1:04
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.