Let $p$ be a prime and $a$ an integer not divisible by $p$. Prove $ax=ay \pmod {p^2}$ implies $x=y \pmod {p^2}$

$p^2$ divides $a(x-y)$ implies $p$ divides $a(x-y)$. $p$ does not divide $a$ implies $p$ divides $x-y$, which implies $x=y \pmod p$

But how does this imply that $x=y \pmod {p^2}$?


You did too many steps. Since $p$ doesn't divide $a$, $gcd(p^2,a)=1$. Thus if $p^2$ divides $a(x-y)$, you have that $p^2$ divides $x-y$ by Euclid's lemma.

Note that you were probably mislead by the fact that the problem gives too much information. This fact is true if you replace $p^2$ by any integer $n$ such that $gcd(n,a)=1$.

  • $\begingroup$ Thanks. I was mislead because I thought Euclid's lemma only worked for primes and $p^2$ isn't prime. But then I realized it can be generalized from prime numbers to any integers: If $n|ab$, and $n$ is relatively prime to $a$, then $n|b$. $\endgroup$ – Borat Sagdiyev Oct 26 '15 at 23:16

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.