# existence and uniqueness of the gcd of two integers

###### Proof.

Let $a,b\in\mathbb{Z}$, where at least one of $a,b$ is nonzero. First we show existence. Define $S=\{ma+nb:m,n\in\mathbb{Z}\text{ and }ma+nb>0\}$. Now clearly $S$ is a subset of natural numbers, and $S$ is also nonempty, for depending upon the signs of $a$ and $b$, we may take $m=n=\pm 1$ to have $ma+nb\in S$. So, by the well-ordering principle for natural numbers, $S$ has a smallest element which we denote $g$. Note that, by construction, $g=m_{0}a+n_{0}b$ for some $m_{0},n_{0}\in\mathbb{Z}$. We will show that $g$ is a greatest common divisor of $a$ and $b$. Suppose first that $g\nmid a$. Then, by the division algorithm for integers, there exist unique $q,r\in\mathbb{Z}$, where $0\leq r, such that $a=qg+r$. By assumption  , $g\nmid a$, so we have

 $0

But then $r$ is an element of $S$ strictly less than $g$, contrary to assumption. Thus it must be that $g\mid a$. Similarly it can be shown that $g\mid b$. Now suppose $h\in\mathbb{N}$ is a divisor   of both $a$ and $b$. Then there exist $k,l\in\mathbb{Z}$ such that $a=kh$ and $b=lh$, and we have

 $g=m_{0}a+n_{0}b=m_{0}kh+n_{0}lh=(m_{0}k+n_{0}l)h\text{,}$

so $h\mid g$. Thus $g$ is a greatest common divisor of $a$ and $b$. To see that $g$ is unique, suppose that $g^{\prime}\in\mathbb{N}$ is also a greatest common divisor of $a$ and $b$. Then we have $g^{\prime}\mid g$ and $g\mid g^{\prime}$, whence $g=\pm g^{\prime}$, and since $g,g^{\prime}>0$, $g=g^{\prime}$. ∎

Title existence and uniqueness of the gcd of two integers ExistenceAndUniquenessOfTheGcdOfTwoIntegers 2013-03-22 16:28:44 2013-03-22 16:28:44 alozano (2414) alozano (2414) 5 alozano (2414) Theorem msc 11-00 GreatestCommonDivisor DivisibilityInRings DivisionAlgorithmForIntegers WellOrderingPrinciple