# Proof of equivalence?

How do I prove that if two numbers $a$ and $N$ are co-prime, then in the equation:

$$ax ≡ ay \pmod N$$

necessarily $x ≡ y \pmod N$

-
(Standard boilerplate): What have you tried? Is this homework? Are you working from a certain course/textbook on number theory? If you can avoid imperative words ("Prove") and favor infinitive questions ("How do I prove...?"), you might find a more fulfilling response from other users! –  The Chaz 2.0 Apr 17 '12 at 1:23
Thanks for the advice! I'll keep it in mind next time. This isn't homework, just a bit of reading I am doing. –  user26649 Apr 17 '12 at 1:36

$ax ≡ ay$ $(mod$ $N$) implies that $ax = ay + pN$ where $p \in \mathbb{Z}$. Then by subtracting $ay$ from both sides, we see that $ax - ay = a(x-y) = pN$. $a$ divides the left hand side of the equation, so it also must divide $pN$. But because $a \mid pN$ and $\gcd(a, N) = 1$, it must be the case that $a \mid p$. So there exists an integer $m$ such that $am = p$.

Then going back to $ax = ay + pN$, we can rewrite it as $ax = ay + (am)N$. If we divide the equation by $a$, we get $x = y + mN$. So we get $x \equiv y$ $(mod$ $N$)

-
You completely lost me after you arrived at a(x-y)= pN. Could you please explain the rest with a bit more detail? –  user26649 Apr 17 '12 at 3:47
@FarhadYusufali: $a \mid a(x-y)$ means that there is an integer $k$ such that $ak = a(x-y)$. Do you see what $k$ should be? Since $a(x-y) = pN$, by substitution we see that $a \mid pN$. Then since we know $a \mid pN$ and $\gcd(a, N) = 1$ that means $a$ and $N$ do not have any factors in common, so $a \mid p$. –  Student Apr 17 '12 at 15:34
Awesome thanks! –  user26649 Apr 17 '12 at 15:53

$ax \equiv ay \mod N \implies N | (ax - ay) \implies N|a(x-y)$

But $N$ doesn't divide $a$, so $N | x-y \implies x \equiv y \mod N$

Here, I used that if $(c,d) = 1$, then $c | de \implies c | e$. If that's not immediately obvious, or known, try to prove that first.

-

Hint $\rm\ (a,n) = 1,\ n\:|\:az\:\Rightarrow\:n\:|\:az,nz\:\Rightarrow\:n\:|\:(az,nz) = (a,n)z = z.\:$ Now put $\rm\:z = x-y.$

-

Hint: If $\gcd(a,b)=1$ then there are $x,y\in\mathbb Z$ so that $ax+by=1$.

-