# Proof involving greatest common divisors

Suppose that $gcd(a,m) = 1$ and $gcd(k,m) = 1$. Show that if $ak \equiv b$ (mod m), then $gcd (b,m) = 1$.

Remarks

We know that $a$ and $m$ are relatively prime. Analogously, we can say the same for the variables $k$ and $m$. By Bezout's Identity, $\exists x_1,y_1 \in \mathbb{Z}$ such that $$ax_1+my_1 = 1.$$

Similarly for variables $k$ and $m$, $\exists x_2,y_2 \in \mathbb{Z}$ such that $$kx_2+my_2 = 1.$$

That is as far as I've gotten.

• If b and m have a factor in common, then do you see that ak will have that as a factor? – fleablood Feb 27 '18 at 3:56

So $0 \leq b < m$ is the unique integer such that $ak \equiv b \mod m$.

Let $l$ be any integer. We will show that $ak + ml$ is co prime to $m$.

To see this, we have $ax_1 + my_1 = 1$ and $kx_2 + my_2 = 1$. Multiplying these gives $$ak(x_1x_2) + m(ax_1y_2 + ky_1x_2 + my_1y_2) = 1$$

and then finally add and subtract $mlx_1x_2$ from the left hand side. Include the addition into the first term, and the subtraction into the second term:

$$(ak+ml)(x_1x_2) + m(ax_1y_2 + ky_1x_2 + my_1y_2 - lx_1x_2) = 1$$

So, by the converse of Bezout's lemma, we see that $ak+ ml$ and $m$, are coprime for all integers $l$. Take $l_0$ to be that integer such that $ak = b + ml_0$. This gives that $ak-ml_0 = b$ and $m$ are coprime.

• Elegant explanation. But just a small remark: co prime and relatively prime are interchangable phrases right? I always hear these two phrases and for some reason believe they are distinct. – Kyogre Feb 27 '18 at 3:53
• They aren't. They mean exactly the same thing. – fleablood Feb 27 '18 at 4:04

Let $d=\gcd (b,m)$

Then if $ak\equiv b\mod m$ that would mean as $d|b$ and $d|m$ we must have $d|ak$.

However as neither $a$ nor $k$ have any factors in common with $m$ (that's what relative prime means), $d$ can't have any factors in common with $ak$. So $d$ must be $1$.