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

Question

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.

Answer 1

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

Answer 2

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