Let $p$ be any prime number, let $a$ be any number coprime to $p$, and let $x$ and $y$ be random integers.
$ax ≡ ay \pmod{p}$
$⇒ay = ax+qp$
$⇒a(y-x) = qp$
Since $a$ divides the left operand, it must divide the right operand. Since $a$ and $p$ are coprime, $a$ must divide $q$, not $p$. Let $m$ represent $q/a$
$⇒x-y = mp$
$⇒y ≡ x \pmod{p}$
I understand why this proves $x$ and $y$ are necessary congruent, but if $a$ and $p$ were not coprime, could $x$ and $y$ still be congruent?
For example, let the the prime factorization of $a$ be $f*g*h$, let the prime factorization of $p$ be $h*i*j$ and let the prime factorization of $q$ be $r*f*g*h$. $a$ and $p$ are obviously not coprime in this situation since they share the factor of $h$.
$ax ≡ ay \pmod{p}$
$⇒ay = ax+qp$
$⇒a(y-x) = qp$
$⇒(f*g*h)(y-x) = (r*f*g*h)(h*i*j)$
$⇒(f*g*h)(y-x) = r*f*g*h*h*i*j$
$⇒y-x = (r*f*g*h*h*i*j)/(f*g*h)$
$⇒y-x = (r)(h*i*j)$
$⇒y ≡ x\pmod{p}$
Since $x$ and $y$ were congruent, but $a$ and $p$ weren't coprime, does this mean that $x$ and $y$ can be congruent even if $a$ and $p$ are not coprime?