2
$\begingroup$

I think the first statement is true and the second statement is false. If so, I want to try to prove the first statement and find a counterexample (or proof) for the second.

  1. If $\exists$ $x,y \in \mathbb Z$ such that $ax+by=c$, then $(a,b)|c$.

  2. If $\exists$ $x,y \in \mathbb Z$ such that $ax+by=c$, then $(a,b)=c$.

Is my intuition right that 1. is true and 2. is false?

$\endgroup$
  • 1
    $\begingroup$ Your intuition looks right to me. $\endgroup$ – Ben West Mar 7 '14 at 3:27
1
$\begingroup$

Recall that $(a,b)$ is the least positive integer that can be written in the form $ax+by$. Note that $(a,b)\mid a,b\implies (a,b)\mid ax+by$. In particular, every common divisor of $a$ and $b$ divides any linear combination $ax+by$.

$\endgroup$
1
$\begingroup$

Your intuition is correct.

Recall that $gcd(a,b)$ divides both $a$ and $b$, so it divides $ax+by$. But 2 is incorrect; here's a counterexample: Let $a=5, b=1, x=1, y=1.$ Then $d=6 \neq gcd(a,b)$.

Fun fact: This is related to Bezout's Lemma.

$\endgroup$
  • $\begingroup$ I'm not sure how that counterexample works. Maybe I am missing something, but if I plug in those numbers I get (5)(1) + (1)(1) = 6, right? So where are you getting d = 5? $\endgroup$ – idkmybffjill Mar 7 '14 at 7:41
  • $\begingroup$ You're right - I changed it. It still doesn't equal the gcd, though. $\endgroup$ – William Chang Mar 7 '14 at 7:43

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.