# Congruence and prime numbers

$P$ is prime number. Prove the only solution for congruence $$x^2 \equiv y^2\pmod{p}$$ are $$x \equiv\pm y\pmod{p}$$ and give an example that exist other solution if n is composite number.

-

## 2 Answers

Hint $\$ By $\rm\: p\:$ prime, $\rm\ p\mid (x\!-\!y)(x\!+\!y)\:\Rightarrow\:p\mid x\!-\!y\ \ or\ \ p\mid x\!+\!y$

Conversely, use $\rm\ 2\mid a\!-\!b\$ $\Rightarrow$ $\rm\ ab\, =\, \left(\dfrac{a+b}2\right)^2 -\left(\dfrac{a-b}2\right)^2\$

For example, for $\rm\, a,b= 5,3\!:\ \ 15 = 4^2\! - 1^2,\$ so $\rm\ 4^2\equiv 1^2,\ 4\not\equiv \pm1\pmod{15}$

-

The congruence $x^2\equiv y^2\bmod p$ is equivalent to the equality $x^2-y^2=0$ in the quotient $\Bbb Z/\Bbb Z p$. But $\Bbb Z/\Bbb Z p$ is a field, thus $$x^2-y^2=(x+y)(x-y)=0$$ implies either $x+y=0$ or $x-y=0$.

As for the counterexample for a composite modulo, $$2^2\equiv 0^2=0 \bmod 4$$ but $2\not\equiv\pm0=0\bmod 4$.

-