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


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.

  • $\begingroup$ If b and m have a factor in common, then do you see that ak will have that as a factor? $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – Kyogre Feb 27 '18 at 3:53
  • $\begingroup$ They aren't. They mean exactly the same thing. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.