# Why is it true that if $ax+by=d$ then $\gcd(a,b)$ divides $d$?

Can someone help me understand this statement:

If $ax+by=d$ then $\gcd(a,b)$ divides $d$.

Bezout's identity states that:

the greatest common divisor $d$ is the smallest positive integer that can be written as $ax + by$

However the definition of $\gcd(a, b)$ is the largest positive integer which divides both $a$ and $b$.

I'm am completely lost. If anyone could provide some sort of layout to help me sort this out I would be really happy.

• What you say is true. What is exactly what you don't understand? Do you want a proof? Examples? Further explanations? – ajotatxe Jul 13 '15 at 19:15
• Hint: write it out. that is, let g be gcd(a,b) and write a = gA and b = gB. – lulu Jul 13 '15 at 19:17

Take a common divisor $k$ of $a$ and $b$. That means that we can write $a=ka'$, $b=kb'$. Then, if $d=ax+by$, $$d=a'kx+b'ky=k(a'x+b'y)$$ so we see that $k$ also divides $d$. Since $\gcd(a,b)$ is a common divisor of $a$ and $b$ (namely, the greatest), it also holds the property. Actually, the idea behind this is very simple: the sum of two multiples of the same number is also a multiple of the same number.
Note that $\gcd(a,b)$ is, hence, the least positive integer that can be written as $ax+by$, because every number of the form $ax+by$ must be a multiple of any common divisor of $a$ and $b$, and in particular, must be a multiple of $\gcd(a,b)$ so $ax+by$ can't be smaller than it (being still positive, of course).
Example: let $a=60$, $b=75$. The gcd is $15$, so $ax+by=60x+75y$ must be a multiple of $15$, because it is the sum of two multiples of $15$.
• so in terms of expressing gcd(a, b) = 15, that means there is a $specific$ x,y that will make ax + by = 15? And 15 is the smallest possible number to come out of the linear combination of a and b? However the gcd(a,b) is also the greatest possible number to divide both a and b? So it is just two different ways of expressing it right? – Rdewolfe Jul 13 '15 at 19:31
Hint: For three numbers $a,b,c$, if $c$ divides $a$ and $c$ divides $b$, then $c$ divides $a+b$.