# 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? – www.data-blogger.com 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 :)! – www.data-blogger.com Sep 27 '12 at 10:59
• how do you see these things xd?. I am not allowed to use math stack exchange in the test XD. If I can't do the work then I just praise the work of others. – TheMathNoob Jun 22 '16 at 7:52
• Doesn't the definition of d = gcd(a,b) imply that d | a and d | b, therefore d | ax + by for any integers x and y. That seems easier than a proof by contradiction. Or is it because we want to show d to be the min S. – john Sep 7 at 21:57
• We might also want to mention that the positive integer set $S$ is nonempty if we set $x=a$ and $y=b$, obtaining $a^2 + b^2 > 0$ since we assume not both $a,b$ are zero, and therefore the minimum exists by the well ordering axiom. Also a corollary seems to be if $ax + by = 1$ for some integers $x$ and $y$, $1$ must be $\gcd(a,b)$ since $1$ is the smallest possible $\min$ for a set of positive integers, and $1$ is attained. – john Sep 8 at 1:57

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 better highlights the implicit ideal structure. This fundamental algebraic 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,\,$$ (which shows that common divisors representable in such linear form are always greatest).

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\:\ell \in S.$$

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

Proof $${\bf\ 2}\,\rm\,\ \ S\,$$ closed under subtraction $$\rm\,\Rightarrow\,S\,$$ closed under remainder (mod), when it is $$\ne 0,$$ since mod is simply repeated subtraction, i.e. $$\rm\ a\ mod\ b\, =\, a - k b\, =\, a\!-\!b\!-\!b\!-\cdots\! -\!b.\,$$ Therefore $$\rm\,n\in S\,$$ $$\Rightarrow$$ $$\rm\, (n\ mod\ \ell) = 0,\,$$ else it is in $$\,\rm S\,$$ and smaller than $$\rm\,\ell,\,$$ contra minimality of $$\rm\,\ell.$$

Remark $$\$$ In a nutshell, two applications of induction yield the following inferences

\begin{align} &\rm S\ \rm closed\ under\ {\bf subtraction}\\[.1em] \Rightarrow\ \ &\rm S\ closed\ under\ {\bf mod} = remainder = repeated\ subtraction \\[.1em] \Rightarrow\ \ &\rm S\ closed\ under\ {\bf gcd} = repeated\ mod\ (Euclidean\ algorithm) \end{align}\qquad\qquad

Interpreted constructively, this yields the extended Euclidean algorithm for the gcd. Namely,  starting from the two elements of $$\rm\,S\,$$ that we know: $$\rm\ a \,=\, 1\cdot a + 0\cdot b,\ \ b \,=\, 0\cdot a + 1\cdot b,\,$$ we search for the least element of $$\rm\,S\,$$ by repeatedly subtracting elements of $$\,\rm S\,$$ to produce smaller elements of $$\rm\,S\,$$ (while keeping track of each elements linear representation in terms of $$\rm\,a\,$$ and $$\rm\,b).\:$$ This is essentially the subtractive form of the Euclidean GCD algorithm (vs. the mod / remainder form), where each reduction / descent step employs subtraction (vs. iterated subtraction = mod).

The conceptual structure will be clarified when one studies ideals of rings, where the above proof generalizes to show that Euclidean domains are PIDs.

Beware  This linear representation of the the gcd 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