If $x^2 \equiv y^2 \pmod {p^r}$, where $p$ is an odd prime not dividing $x$ or $y$ then $x \equiv \pm y \pmod {p^r}$

If $x^2 \equiv y^2 \pmod {p^r}$ then $p^r \mid x^2 - y^2$ and so $p^r\mid(x-y)(x+y)$. Now since $p$ is a prime that is not dividing $x$ nor $y$ then it's easy to see that $p^r \nmid x$ and also $p^r \nmid y$. Now I was wondering if this implied in particular that $p^r$ doesn't divide any linear combination of $x$ and $y$ ?

But This is certainly not true. Because we have that $3 \nmid 5$ and $3 \nmid 7$ however we have that $3 \mid 5 + 7 =12$.

I wanted to apply Euclids lemma but now I am stuck here.

Solution 1:

Assume for contradiction that $x \not\equiv \pm y \pmod{p^r}$.

Since $x^2 \equiv y^2 \pmod {p^r}$, it follows that $(x+y)(x-y)=0 \in \mathbb{Z}/(p^r)$. Therefore, both $x+y$ and $x-y$ are zero divisors in $\mathbb{Z}/(p^r)$, i.e, they are nonzero elements in $\mathbb{Z}/(p^r)$ whose product is $0$.

But the only zero divisors in the ring $\mathbb{Z}/(p^r)$ are the multiples of $p$. Therefore both $x+y$ and $x-y$ must be multiples of $p$. Therefore $2x = (x+y)+(x-y) $ must be a multiple of $p$, and similarly $2y=(x+y)-(x-y)$ must be a multiple of $p$ as well. Thus $p|2x$ and $p|2y$, so since $p$ is odd it follows that $p|x$ and $p|y$, which gives the desired contradiction (since we assumed that $p$ doesn't divide $x$ or $y$).