5
$\begingroup$

Can someone provide the proof that $x^2$ $\equiv$ $1$ $\mod{p}$ iff $x\equiv1 \mod{p}$ or $x\equiv p-1 \mod{p}$, where $p$ is a prime? The argument I have in mind is setting up a bijection, like in the proof Euler's Theorem, and then restricting the case somehow to only the elements such that $x^2 \equiv 1$.

$\endgroup$
5
$\begingroup$

We have $p \mid (x^2-1) \implies p \mid (x-1)(x+1)$. By definition of a prime, if $p \vert ab$, then $p \mid a$ or $p \mid b$.

Hence, $p \mid (x^2-1) \implies p \mid (x-1) \text{ or } p \mid (x+1)$.

The other way is trivial.

$\endgroup$
0
$\begingroup$

If $x=p+1$, then does $x^2$ $\equiv$ $1$ $\mod{p}$ hold? There are many solutions to the question. $x$ don't need to be only $1$ or $p-1$.

$\endgroup$
  • $\begingroup$ I should amend my statement, I suppose. I meant equivalent to. $\endgroup$ – user82004 Nov 21 '14 at 1:16

Your Answer

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