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$
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$
$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$)
$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$.