0
$\begingroup$

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?

  • 0
    It doesn't really matter, but you switched the sign of $q$ halfway through: it should be $a(y-x)=qp$.2012-04-24

1 Answers 1

1

For all $\rm\:a\:$ it is true that $\rm\:x\equiv y\ \Rightarrow\ ax\equiv ay\:$ since $\rm\:p\ |\ x-y\ \Rightarrow\ p\ |\ a\:(x-y) = ax-ay.$

This direction does not require that $\rm\:(a,p) = 1,\:$ as does the converse.

  • 0
    Understood, thank you!2012-04-25