# If $\exists$ $x,y \in \mathbb Z$ such that $ax+by=c$, then does $(a,b)|c$ or even stronger does $(a,b)=c$?

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?

• Your intuition looks right to me. – Ben West Mar 7 '14 at 3:27

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

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.

• 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? – idkmybffjill Mar 7 '14 at 7:41
• You're right - I changed it. It still doesn't equal the gcd, though. – William Chang Mar 7 '14 at 7:43