0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.