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

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

I'm a little confused with your second line of reasoning. Of course $p^r$ can divide a linear combination of x,y. Multiply x and y by $p^r$ and add them together. Restrict yourself to working mod $p^r$.

clearly $p^r$ | $p^r$x + $p^r$y

Your intuition is correct, you're supposed to use Euclid's lemma.

If $p^r$|x+y, where x,y $\in$ $\Bbb{Z}_{p^r}^*$ then x,y < $p^r$ therefore, 2 < x+y < 2$p^r$-2 so, $p^r$|x+y only if x+y = $p^r$. Therefore, y= $p^r$-x $\to$ y=-x mod $p^r$. On the other hand, if $p^r$|x-y, taking x ≥ y wlog, we know 0 ≤ x-y ≤ $p^r$-1.Thus, $p^r$|x-y only if x-y=0 so, x=y.

To check Euclid's lemma applies, If x=-y, then x-y = 2x, which is coprime with $p^r$
on the other hand, if x=y, then x+y = 2x which is again coprime with $p^r$.