# Interpretation of $\gcd(a,b) = ax + by$

The greatest common divisor of $a, b \in \mathbb{Z}$ can always be expressed as a linear combination of $a$, $b$. Furthormore, $\gcd(a,b)$ has the smallest magnitude of any number of the form $z = ax + by$

Please excuse my difficulties with mathematics. But this is something I keep coming back to again and again, and yet still can't reconcile this fact.

I understand the proof perfectly well... but if someone were to ask whats really going on here? or to give a heuristic/intuition on why this is really true, I wouldn't be able to answer.

In math, typically one has an idea, then uses a proof as a means of explaining why the idea is true. What I'm looking for, is the intuition behind the idea.

Thanks for any help in this, albeit embarrassingly simple problem.

-
Oops, sorry. I'll edit – user45793 Nov 8 '12 at 6:24
Which proof is it that you saw? – Zach L. Nov 8 '12 at 6:29
showing that if z is the least positive integer of the set S ={ax+by|x,y integers}, then z|a, z|b, and z divides any common divisor of a, b. Thus z = gcd(a,b). The proof basically goes as: if z doesn't divide a and b, then there is a smaller number in S than z – user45793 Nov 8 '12 at 6:33
Do you Know anything about ideals? The proof you are referring to is $(a)+(b)=(\gcd(a,b))$. – P.. Nov 8 '12 at 6:35
I've been educated on them, but I don't know anything about them. If you get what I mean lol. – user45793 Nov 8 '12 at 6:38

Consider the two numbers, $a$ and $b$, say they are not both zero. Each of them generates a subgroup of $\mathbb Z$: the set of all multiples of $a$ and of $b$, respectively. We usually denote these sets $a\mathbb Z$ and $b\mathbb Z$. But what subgroup of $\mathbb Z$ do $a$ and $b$ together generate? In more down-to-earth terms, what are all the numbers $ax+by$ as $x$ and $y$ range over all possible integers? They make up a set that is a subgroup of $\mathbb Z$, as you see easily: add or subtract two numbers of that form and of course you get another. But it drops out of the Euclidean property of the integers that this new subgroup is the set of all multiples of some particular positive integer $g$.

Now let's back up a bit. You can easily check that $m\mathbb Z\supset n\mathbb Z$ if and only if $m$ divides $n$, $m|n$. In particular if $g$ is the generator of the set of all $ax+by$ then $g|a$ and $g|b$. A little thought shows you that $g$ is the biggest integer dividing both, too: it’s the greatest common divisor of $a$ and $b$.

-
Thats so cool.. everything I hoped for in an explanation. Thanks so much! – user45793 Nov 8 '12 at 6:45

The set $\rm\:S\:$ of integers of the form $\rm\:x\:a + y\:b,\ x,y\in \mathbb Z\:$ is closed under subtraction so, by the Lemma below, every $\rm\:n\in S\:$ is divisible by the least positive $\rm\:d\in S.\:$ Thus $\rm\:a,b\in S\:$ $\Rightarrow$ $\rm\:d\:|\:a,b,\:$ i.e. $\rm\:d\:$ is a common divisor of $\rm\:a,b,\:$ necessarily greatest, by $\rm\:c\:|\:a,b\:$ $\Rightarrow$ $\rm\:c\:|\:d =\hat x\:a+\hat y\:b\:$ $\Rightarrow$ $\rm\:c\le d.$

Lemma $\ \$ If a nonempty set of positive integers $\rm\: S\:$ satisfies $\rm\ n > m\ \in\ S \ \Rightarrow\ \: n-m\ \in\ S$
then every element of $\rm\:S\:$ is a multiple of the least element $\rm\:m_{\:1} \in S.$

Proof $\ \:$ If not there is a least nonmultiple $\rm\:n\in S,\,$ contra $\rm\:n-m_{\:1} \in S\:$ is a nonmultiple of $\rm\:m_{\:1}.$

Remark $\$ This fundamental lemma, interpreted procedurally, yields Euclid's classical algorithm to compute the gcd using only repeated subtraction.

This linear representation of the the gcd is known as the Bezout identity for the gcd. This exists in any domain that, like $\Bbb Z,\,$ enjoys division with "smaller" remainder - so-called  Euclidean domains. But this need not hold true in all domains where gcds exist, e.g. in the domain $\rm\:\mathbb Q[x,y]\:$ of polynomials in $\rm\:x,y\:$ with rational coefficients we have $\rm\:gcd(x,y) = 1\:$ but there do not exist $\rm\:f,\: g\in \Bbb Q[x,y]\:$ with $\rm\:x\:f + y\:g = 1;\:$ indeed, if so, then evaluating at $\rm\:x = 0 = y\:$ yields $\:0 = 1.$

-
Thanks for the reply! Sorry, I think I marked Lubin's post correct as you were typing this one. Another great way of thinking about it! Much appreciated! – user45793 Nov 8 '12 at 6:55