Prove $ax=ay \pmod {p^2}$ implies $x=y \pmod {p^2}$

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$.
• 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$. – Borat Sagdiyev Oct 26 '15 at 23:16