# Show the congruence $x^{p-1}\equiv 1\pmod{p}$ has $p-1$ solutions

Question: Let $p$ be prime. show the congruence $x^{p-1}\equiv 1\pmod{p}$ has $p-1$ solutions

Attempt: I know by Lagrange's theorem that this congruence will have at most $p-1$ solutions since $p-1$ is the order of the congruence

I know by Fermat's little theorem that if $(x,p)=1$ then $x^{p-1}\equiv 1\pmod{p}$

I know I will have to combine Lagrange's theorem and FLT, but I cant see how there is exactly $p-1$ solutions

• Hint: How many numbers $x$ from $0$ to $p-1$ satisfy $(x,p) = 1$? – Darth Geek May 11 '15 at 10:11
• I'd say that congruence has infinite many solutions... do you mean in the prime field $\;\Bbb F_p\;$ or where ? – Timbuc May 11 '15 at 10:13
• @DarthGeek I must be quite tired, totally understand now, there are $p-1$ solutions, thanks – Sam Houston May 11 '15 at 10:14
• Maybe I have misunderstood the question, but if x can be larger than or equal to p, this seems not to hold. eg. take $p=5$, $6^{5-1} \equiv 1$. – k99731 May 11 '15 at 10:14
• @Timbuc I just assumed by the context that we are working $\pmod{5}$ – Sam Houston May 11 '15 at 10:23

Assuming we are working in $\mathbb{Z}/p\mathbb{Z}$.
On the one hand, by Lagrange's Theorem, said congruence has at most $p-1$ solutuions
On the other hand, by Fermat's Little Theorem, if $(x,p) = 1$ then $x^{p-1}\equiv 1\pmod p$.
Since the only element that does not satisfy $(x,p) = 1$ is $0$, then the remaining $p-1$ elements are solutons to the congruence.
In $\mathbb{F}_p$ which is cyclic, we look at the morphism $\mathbb{F}_p^{\times}\to \mathbb{F}_p^{\times}$, $x\mapsto x^{p-1}$ and the kernel.
$Card\{x\in \mathbb{F}_p^{\times} \mid x^{p-1}\equiv 1 \pmod p\}=\gcd(p-1,p-1)=p-1$.