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$
11
  • 6
    $\begingroup$ Hint: How many numbers $x$ from $0$ to $p-1$ satisfy $(x,p) = 1$? $\endgroup$
    – Darth Geek
    May 11, 2015 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, 2015 at 10:13
  • 1
    $\begingroup$ @DarthGeek I must be quite tired, totally understand now, there are $p-1$ solutions, thanks $\endgroup$ May 11, 2015 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, 2015 at 10:14
  • 1
    $\begingroup$ @Timbuc I just assumed by the context that we are working $\pmod{5}$ $\endgroup$ May 11, 2015 at 10:23

2 Answers 2

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .