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 Jun 12 '17 at 19:57

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ 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. $\endgroup$ – Chessanator Jun 12 '17 at 17:07
  • $\begingroup$ I see.. Any hints? $\endgroup$ – dumb_undergrad Jun 12 '17 at 17:21
  • 1
    $\begingroup$ Have you seen yet that the gcd of a and m is a linear combination of them? $\endgroup$ – Chessanator Jun 12 '17 at 17:24
  • $\begingroup$ Yes, that's what DonAntonio used bellow, I understand. Thanks! $\endgroup$ – 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)$$

and we have a solution.

  • $\begingroup$ That completes my proof, as Chessnator said above, I've done only half of it. Now, how does that show we have a solution? $\endgroup$ – dumb_undergrad Jun 12 '17 at 17:35
  • $\begingroup$ @dumb_undergrad I don't understand: in the above it is clear that $\;x=cr,\,y=cs\;$ is a solution... $\endgroup$ – DonAntonio Jun 12 '17 at 19:36
  • $\begingroup$ Oh, right, thanks! $\endgroup$ – dumb_undergrad Jun 12 '17 at 19:43

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