Let $d,\ a,\ x,\ b,\ y $ be integers. $d$ divides $a$ and $b$.

The question is: Assume $ax + by \gt 0$. Prove or disprove : $d \le ax + by $

I know that $d | ax+by$, but I can't figure out the proof for why $d$ would be $\le ax+by$.

  • $\begingroup$ Is it because d = GCD(a,b) and that will always be less than a and b? $\endgroup$
    – CloudN9ne
    Oct 5, 2014 at 4:09
  • $\begingroup$ Would the statement be true if we stuck with natural numbers? Keep in mind we're working with integers. $\endgroup$
    – Squirtle
    Oct 5, 2014 at 4:10
  • 1
    $\begingroup$ ^In response to my above comment.... combine this with your assumption "$ax+by>0$. can you come up with counterexamples if this isn't true? $\endgroup$
    – Squirtle
    Oct 5, 2014 at 4:12
  • $\begingroup$ No. $a | (-a)$ and $(-a) | a$. $\endgroup$
    – Squirtle
    Oct 5, 2014 at 4:15

1 Answer 1


$d| (ax+by) $ so that $$ ax+by=dn$$ If $ ax+by >0$, then $$n\neq 0,\ ax+by=|dn| \geq d $$


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.