Greatest common divisor algorithm

Question

I am having some issues understanding the gcd. I am using "Art of Proof," and in this book, the gcd(m,n) is defined as being:

"the smallest element of the set S = {k $\in$ N : k = mx+ny for some x, y $\in$ Z}

I guess my issue is that I don't really understand what k=mx+ny is in the context of gcd.

To provide some context for my confusion, we are asked to use the gcd definition when we prove various things about prime numbers and specifically Euclid's lemma. I have been struggling with this and I think part of it is because I don't really understand the algorithmic definition of gcd.

Answer 1

If we take as definition of the g.c.d. of $m$ and $n$: ‘the greatest natural number which is a divisor of both $m$ and $n$, the smallest element of $S$ satisfies this definition.

Indeed, let's denote $d$ this smallest element non-zero of $S$. Thus, we have $d=xm+yn$ for some $x,y\in\mathbf Z$. Perform the Euclidean division of $m$ by $d$: $$m=qd+r,\quad 0\le r<d$$ We deduce that $$ r=m-qd=(1-qx)m-(qy)n\in S. $$ As $d$ is the smallest positive element of S, this relation implies $r=0$. In other words, $d$ divides $m$. For similar reasons, $d$ divides $n$.

On ther other hand, $d$ is the greatest common divisor of $m$ and $n$, since if $d'\mid m$ and $d'\mid n$, $d'$ divides any linear combination of $m$ and $n$ – in particular, it divides $d$.

Answer 2

A theorem known as Bezut's Lemma says that that definition is equivalent to the following definition:

Definition (gcd): A GCD of two integers, $a,b$ is a number $c$ such that $c$ is a common divisor of $a$ and $b$, and for any other common divisor, $d$, we have that $d|c$. We denote this as $gcd(a,b)=c$

The intuition for this theorem comes from lattices. Think about the number line, and put a penny on $0$. If you are only allowed to move up and down the number line in steps of size $a$, then it should be clear that you can only reach multiples of $a$.

Now imagine that we are allowed to use two different step sizes, $a$ and $b$. By moving up $a$ and then down $b$ we wind up closer to $0$ than either $a$ or $b$ alone. The set of all points we can reach with these two step sizes is guaranteed to have a smallest positive value, since every non-empty set of positive integers does. Let's call this number $d$. We got to $d$ using steps of size $a$ and $b$, so $ax+by=d$ holds for some numbers $x$ and $y$. Thus thus number $d$ is the smallest element of the set in your definition.

That's the intuition for what the set and what it's smallest positive element means. Just like in the case of steps of size $a$, the set in question turns out to be the set of all multiples of $d$. Proving that this is equal to the other sense of GCD isn't particularly hard, but does require a little work and the Euclidean Algorithm. You can easily find such proofs by searching this website or google for Bezut's Lemma.