Question

Prove or disprove: If$a^2\equiv b^2\left(modn\right)$ , then$a\equiv b\left(modn\right)$ or$a\equiv -b\left(modn\right)$ .

(b) Do part (a) when$n$ is prime.

Short answer

It is proved that$\left(a,n\right)=\left(b,n\right)$ .

Step-by-step solution

Prove or disprove that  if  a2≡b2 mod n, then a≡b mod n or a≡-b mod n 

It is given that$a^2\equiv b^2\left(modn\right)$ to prove or disprove$a\equiv b\left(modn\right)$ or$a\equiv -b\left(modn\right)$ .

As $a^2\equiv b^2\left(modn\right)$, this implies that$\overline{)n}\left(a^2-b^2\right)$ , that is $\overline{)n}\left(a-b\right)\left(a+b\right)$,

Consider $a=4,b=1$, and $n=15$, this implies that

$4^2\equiv 1^2\left(mod15\right)$

.

But we can observe that $\overline{)15}4$and$\overline{)15}1$ .

Hence, if $a^2\equiv b^2\left(modn\right)$, then neither $a\equiv b\left(modn\right)$or$a\equiv -b\left(modn\right)$ .

Prove or disprove that if a2≡b2 mod n , then a≡b mod n  , or a≡-b mod n when n is prime

It is given that$a^2\equiv b^2\left(modn\right)$ to prove or disprove$a\equiv b\left(modn\right)$ ,or$a\equiv -b\left(modn\right)$ when$n$ is prime.

Since $n$is prime and $a^2\equiv b^2\left(modn\right)$, this implies that

$\overline{)n}\left(a-b\right)\left(a+b\right)$.

Then according to theorem, an integer$p$ is prime if and only if$p$ has the property whenever$\overline{)p}bc$ , then$\overline{)p}b$ or$\overline{)p}c$ .

UsingTheorem$\overline{)n}\left(a-b\right)$ or$\overline{)n}\left(a+b\right)$ ,this means that$a\equiv b\left(modn\right)$ or$a\equiv -b\left(modn\right)$ .

Hence, it is proved that$a^2\equiv b^2\left(modn\right)$ , then$a\equiv b\left(modn\right)$ , or$a\equiv -b\left(modn\right)$ when$n$ is prime.