4
$\begingroup$

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$

  • 0
    Thanks for the advice! I'll keep it in mind next time. This isn't homework, just a bit of reading I am doing.2012-04-17

4 Answers 4

0

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

  • 0
    @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$.2012-04-17
2

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

1

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

0

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