existence and uniqueness of the gcd of two integers

Theorem.

Given two integers, at least one different from zero, there exists a unique natural number satisfying the definition of the greatest common divisor.

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 , such that $a=qg+r$. By assumption, $g\nmid a$, so we have

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