# 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+nb0\}$. 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}$. ∎

Title | existence and uniqueness of the gcd of two integers |
---|---|

Canonical name | ExistenceAndUniquenessOfTheGcdOfTwoIntegers |

Date of creation | 2013-03-22 16:28:44 |

Last modified on | 2013-03-22 16:28:44 |

Owner | alozano (2414) |

Last modified by | alozano (2414) |

Numerical id | 5 |

Author | alozano (2414) |

Entry type | Theorem |

Classification | msc 11-00 |

Related topic | GreatestCommonDivisor |

Related topic | DivisibilityInRings |

Related topic | DivisionAlgorithmForIntegers |

Related topic | WellOrderingPrinciple |