0
$\begingroup$

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

2

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

3

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