# 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? Jul 13, 2015 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, 2015 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$.

I hope this helps a bit.

• 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? Jul 13, 2015 at 19:31

Hint: For three numbers $a,b,c$, if $c$ divides $a$ and $c$ divides $b$, then $c$ divides $a+b$.

I'd like to offer a perspective from algebra that made it click for me. Consider John B. Fraleigh's definition from 'Introduction to Abstract Algebra':

Let $$r$$ and $$s$$ be two positive integers. The positive generator $$d$$ of the cyclic group $$H = \{nr + ms \mid m,n \in \mathbb{Z}\}$$ under addition is the $$\textbf{greatest common divisor}$$ of $$r$$ and $$s$$.

Let's consider a numeric example, same as above: $$r = 60$$ and $$s = 75$$. Their gcd is obviously $$d = 15$$ and all the multiples of $$15$$ are in $$H$$: $$(k)(75)+(-k)(60) = 15k \in H, k \in \mathbb{N}$$. Let's show that there are no integers smaller than $$d$$ in $$H$$.

Suppose to the contrary that there exists an integer $$c \in \mathbb{N}$$ such that $$c < d$$ and $$c \in H$$. Then $$c = nr + ms$$. Since $$d$$ divides $$r$$ and $$s$$, we can write $$r = di$$ and $$s = dj$$ for some $$i,j \in \mathbb{N}$$. Now $$c = ndi + mdj$$, which means $$\frac{c}{d} = ni + mj \in \mathbb{Z}$$, which is a contradiction as our assumption meant $$0<\frac{c}{d} < 1$$.

So there are no positive integers smaller than $$d \in H$$. Since $$d$$ divides every number of the form $$nr + ms$$ and is the smallest positive element, it generates the set.