Monday, 5 January 2026

Exercise (4.2).11

Show that $x^2 \equiv 1 \pmod {n}  \;\not\!\!\!\implies  x \equiv \pm 1 \pmod {n}$.


We show this with a counter-example.

Consider $x \equiv 3 \pmod 8$. 

$$  3^2 \equiv 9  \equiv 1 \pmod 8 $$

Here $x^2 \equiv 1 \pmod n$, but $x \not \equiv \pm 1 \pmod n$. 


Note that $x^2 \equiv 1 \pmod {n}  \implies  x \equiv \pm 1 \pmod {n}$ only if $n$ is prime, as we have shown in a previous exercise.