Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
It doesn't really matter, but you switched the sign of $q$ halfway through: it should be $a(y-x)=qp$. – Generic Human Apr 24 '12 at 23:19
Thanks, fixed it. – user26649 Apr 24 '12 at 23:28
up vote 1 down vote accepted

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.

share|cite|improve this answer
Thanks. I'm a little confused-is my assumption $x$ and $y$ can be congruent if $a$ and $n$ are not prime true? – user26649 Apr 25 '12 at 0:31
Sure, as above, choose any $\rm\:x\equiv y\:$ and any $\rm\:a\equiv 0.$ – Bill Dubuque Apr 25 '12 at 0:38
But why does $a$ HAVE to be zero? My example above doesn't have an $a$ thats equal to zero. – user26649 Apr 25 '12 at 0:44
@Farhad In your example $\rm\ a\:(x-y) = pq\ $ so $\rm\ (x-y)/p = q/a\ $ so $\rm\ p\:|\:x-y\iff a\:|\:q.\:$ Your example is constructed so that $\rm\:a\:|\:q\:$ hence $\rm\:p\:|\:x-y.\:$ If you want $\rm\:p\:|\:a(x-y)\:$ but $\rm\:p\nmid a,x-y\:$ then choose non-prime $\rm\:p = ab,\:$ and $\rm\:x-y = b.$ – Bill Dubuque Apr 25 '12 at 1:23
Understood, thank you! – user26649 Apr 25 '12 at 2:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.