# Show that $ax \equiv b (mod\ m)$ has solution iff $gcd(a,m)$ divides $b$ [duplicate]

This question already has an answer here:

Here's what I have:

$ax \equiv b (mod\ m)$ has answer if there are $x$ and $y$ such that

$b = ax + my$

Let $d = gcd(a,m)$. Then:

$d|a$ and $d|m \Leftrightarrow d|ax$ and $d|my \Leftrightarrow d|(ax+my)$

Since $m$ divides the right part of the equation, it also has to divide the left part.

Is this a valid proof for what I want?

## marked as duplicate by Bill Dubuque elementary-number-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jun 12 '17 at 19:57

• You have half of it: "If there is a solution, then d divides b." You also need to show that whenever b is a multiple of d, you have a solution. – Chessanator Jun 12 '17 at 17:07
• I see.. Any hints? – dumb_undergrad Jun 12 '17 at 17:21
• Have you seen yet that the gcd of a and m is a linear combination of them? – Chessanator Jun 12 '17 at 17:24
• Yes, that's what DonAntonio used bellow, I understand. Thanks! – dumb_undergrad Jun 12 '17 at 17:34

If $\;d=gcd(a,m)\;$, then there exist $\;r,s\in\Bbb Z\;$ s.t. $\;ra+sm=d\;$ , so
$$b=cd\implies b=c(ra+sm)=a(cr)+m(cs)$$
• @dumb_undergrad I don't understand: in the above it is clear that $\;x=cr,\,y=cs\;$ is a solution... – DonAntonio Jun 12 '17 at 19:36