3
$\begingroup$

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

$\endgroup$
  • 6
    $\begingroup$ Hint: How many numbers $x$ from $0$ to $p-1$ satisfy $(x,p) = 1$? $\endgroup$ – Darth Geek May 11 '15 at 10:11
  • $\begingroup$ I'd say that congruence has infinite many solutions... do you mean in the prime field $\;\Bbb F_p\;$ or where ? $\endgroup$ – Timbuc May 11 '15 at 10:13
  • 1
    $\begingroup$ @DarthGeek I must be quite tired, totally understand now, there are $p-1$ solutions, thanks $\endgroup$ – Sam Houston May 11 '15 at 10:14
  • 1
    $\begingroup$ 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$. $\endgroup$ – k99731 May 11 '15 at 10:14
  • 1
    $\begingroup$ @Timbuc I just assumed by the context that we are working $\pmod{5}$ $\endgroup$ – Sam Houston May 11 '15 at 10:23
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$.

$\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.