Proof involving greatest common divisors

Question

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.

Answer 1

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.

Answer 2

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