How to show that the $x^a \equiv 1 \pmod p$ has exactly $\gcd(a,p-1)$ solutions at $Z^*_{p}$?

253 Views Asked by At

It is given that $p$ is prime number and $a\ge1$

solution so far:

$x^{\gcd(a,p-1)} ≡ 1$ because it known that a group of units of $Z/pZ$ is cyclic and of order $n=p-1$ for $p$ prime, and also in a cyclic group of order $n$, $x^a = x^{\gcd(a, n)}$ for all elements $x$ and exponents $a$.

Also in an arbitrary group, $x^a = 1$ implies that $|x| \mid a$. (Lagrange's theorem in the case of cyclic groups) so $x \mid \gcd(a,p-1) $ So, to count valid $x$'s, we just need to count the number of elements of order $d$ where $d \mid \gcd(a,p-1)$, and add up those results

Let's say that $b = \gcd(a, p-1) = \gcd(a, n)$, so $b \mid n$ by construction. Also, if $d\mid b$, then $d\mid n$. There are $\varphi(d)$ solutions for a given $d\mid b$ because a cyclic group of order $n$ has $\varphi(d)$ elements of order $d$, assuming $d$ divides $n$.

So the total number of solutions is $\sum\limits_{d\mid b}\varphi(d)$ but it is known that $\sum\limits_{d\mid b}\varphi(d) = b$ is valid, where the sum is taken over positive divisors $d$ of $b$ and $b = \gcd(a,p-1)$

Is that correct, is there a better way to solve it?

1

There are 1 best solutions below

1
On

There is (perhaps) a better way to solve it. Let $g$ be a primitive root mod $p$ and $1=g^b$, $x=g^y$. Then $x^a\equiv 1$ mod $p$ is equivalent to $g^{ay}\equiv g^b$ mod $p$, which is equivalent to the linear congruence $ay\equiv b$ mod $p-1$. This linear congruence has exactly $gcd(a,p-1)$ solutions.