Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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

1 Answer 1

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|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

 
discard

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