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 '14 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 '14 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 '14 at 4:12
  • $\begingroup$ No. $a | (-a)$ and $(-a) | a$. $\endgroup$ – Squirtle Oct 5 '14 at 4:15

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