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

Here is my proof of $\gcd(a,b)=ax+by$ for $a, b, x, y \in \mathbb{Z}$. Am I doing something wrong? Are there easier proofs?

$a,b \in \mathbb{Z}, g=\gcd(a,b)$ and suppose $g \neq ax + by$. Let $c$ be a common divisor of $a$ and $b$. Then

$$\forall x', y' \in \mathbb{Z}: c | ax' + by'\Longrightarrow\exists q_1, q_2 \in \mathbb{Z}\,\,\, s.t.\,\,\, c q_1 = ax' + by'\,\,,\,\,cq_2 = g$$

So

$$gcd(a, b)=g=c q_2 = c q_1 \frac{q_2}{q_1} = \left(\frac{q_2}{q_1}x'\right)a + \left(\frac{q_2}{q_1}y'\right)b$$ So if we have $q_1|q_2$ then we found $\gcd(a,b)=ax'+by'$ for all $x', y' \in \mathbb{Z}$.

Now

$$\frac{q_1}{q_2}=\frac{c q_1}{c q_2} = \frac{ax'+by'}{g}$$ but $g|a$ and $g|b$ so $\exists q_3 \in \mathbb{Z}: \frac{q_1}{q_2}=q_3 \Rightarrow q_1=q_2 q_3 \Rightarrow q_1 | q_2\,$ . QED.

-
What you've done wrong is, you haven't given a careful statement of what you are trying to prove. What are $a,b,x,y$? Are you asserting that equality for all $a,b,x,y$? or should there be some existential quantifiers somewhere? A proof is only as good as the statement of what it's proving. –  Gerry Myerson Sep 27 '12 at 10:50
Also: you assert $\gcd(a,b)=ax'+by'$ for all integers $x',y'$, but that's clearly false. Also: $q_1=q_2q_3$ surely does not imply $q_1$ divides $q_2$. –  Gerry Myerson Sep 27 '12 at 10:54
Ah, I see. It is for some integers. But how can I proof it? Am I on the right track or should I try something completely different? –  Kevin Sep 27 '12 at 10:55
Why don't you look into an Elementary Number Theory book ? –  Ralph Sep 27 '12 at 10:57
To begin with, you should try to write a clear and correct statement of what you are trying to prove. There's no point worrying about how to prove when you don't know what to prove. –  Gerry Myerson Sep 27 '12 at 11:00

The nicest proof I know is as follows:

Consider the set $S = \{ax+by>0 : a,b \in \mathbb{Z}\}$. Let $d = \min S$. We now show the following:

• $d$ is a common divisor of $a$ and $b$.
• Any common divisor of $a$ and $b$ must divide $d$.

If we can show those two things then it is trivial that $d$ is the greatest common divisor of $a$ and $b$, and therefore that the greatest common divisor of $a$ and $b$ is of the form $ax+by$.

To show that $d$ divides $a$ and $b$: suppose for a contradiction that $d$ does not divide $a$. Then $a=qd+r$, where $q\ge 0$ and $0<r<d$. Since $a=qd+r$, $qd=a-r$, and since we have that $d=ax+by$, $q(ax+by)=a-r$, so $r=a(1-qx)-bqy$. So $r$ is a linear combination of $a$ and $b$, and since $r>0$, that means that $r\in S$. Since $r<d$ and we had supposed $d$ to be $\min S$, we have a contradiction. So $d$ must divide $a$.

An identical argument proves that $d$ must divide $b$.

We now want to show that any common divisor of $a$ and $b$ must divide $d$. This is easy to show: if $a=uc$ and $b=vc$, then $d=ax+by=c(ux+vy)$, so $c$ divides $d$.

Therefore, $d$ is the greatest common divisor of $a$ and $b$, and is of the form $ax+by$.

-
Wow, astonishing :D! That division with remainder did the trick here :)! Thanks :)! –  Kevin Sep 27 '12 at 10:59

You ask what is the easiest proof of the linear representation of the gcd (Bezout's Identity). In my opinion it is the proof below, which also has much to offer conceptually, since it hints at the implicit ideal structure. This fundamental structure will come to the fore in later studies.

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. It need not hold true in all domains where gcds exist, e.g. in the domain $\rm\:D = \mathbb Q[x,y]\:$ of polynomials in $\rm\:x,y\:$ with rational coefficients we have $\rm\:gcd(x,y) = 1\:$ but there are no $\rm\:f(x,y),\: g(x,y)\in D\:$ such that $\rm\:x\:f(x,y) + y\:g(x,y) = 1;\:$ indeed, if so, then evaluating at $\rm\:x = 0 = y\:$ yields $\:0 = 1.$

-
@ Bill Dubuque, what is the abstract reason that makes this fail in some domains? Is it that they cannot be well-ordered in a way that is compatible with the ring operations? –  Martin Berger Sep 28 '12 at 14:01
@Martin Generally any Euclidean domain is Bezout, i.e. any domain that has an algorithm for division with "smaller" remainder has linear representable gcds, i.e. satisfies Bezout's Identity. Here the size valuation on the remainders can take values in any well-ordered set. This can fail for various reasons, e.g. if two nonzero elements fail to have a gcd, as in the example above. –  Bill Dubuque Sep 28 '12 at 14:18