9
$\begingroup$

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.

  • 5
    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.2012-09-27
  • 0
    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$.2012-09-27
  • 0
    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?2012-09-27
  • 1
    Why don't you look into an Elementary Number Theory book ?2012-09-27
  • 1
    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.2012-09-27
  • 0
    You can use Euclid's algorithm to prove your statement, and doing so, you can explicitly find $x$ and $y$.2012-09-27
  • 0
    I think that would be correct: "Let's $\; g=\gcd(a,b)$. Supose that for all $ a,b\in\mathbb{Z}\; $ that $g \neq ax + by$." in place of "$a,b\in \mathbb{Z},\;g=\gcd(a,b)$ and suppose $g\neq ax+by$."2013-01-15

2 Answers 2

16

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

  • 0
    Wow, astonishing :D! That division with remainder did the trick here :)! Thanks :)!2012-09-27
  • 0
    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.2016-06-22
5

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

Proof ${\bf\ 1}\,\ $ If not there is a least nonmultiple $\,n\in 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

$ \rm\begin{eqnarray} S\ \rm closed\ under\ {\bf subtraction} &\:\Rightarrow\:&\rm S\ closed\ under\ {\bf mod} = remainder = repeated\ subtraction \\ &\:\Rightarrow\:&\rm S\ closed\ under\ {\bf gcd} = repeated\ mod\ (Euclid's\ algorithm) \end{eqnarray}$

Interpreted constructively, this yields the extended Euclidean algorithm for the gcd.

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

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

  • 0
    @ 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?2012-09-28
  • 2
    @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.2012-09-28