existence and uniqueness of the gcd of two integers


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


Let a,b, where at least one of a,b is nonzero. First we show existence. Define S={ma+nb:m,n 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=±1 to have ma+nbS. So, by the well-ordering principle for natural numbers, S has a smallest element which we denote g. Note that, by construction, g=m0a+n0b for some m0,n0. We will show that g is a greatest common divisor of a and b. Suppose first that ga. Then, by the division algorithm for integers, there exist unique q,r, where 0r<g, such that a=qg+r. By assumptionPlanetmathPlanetmath, ga, so we have


But then r is an element of S strictly less than g, contrary to assumption. Thus it must be that ga. Similarly it can be shown that gb. Now suppose h is a divisorMathworldPlanetmathPlanetmath of both a and b. Then there exist k,l such that a=kh and b=lh, and we have


so hg. Thus g is a greatest common divisor of a and b. To see that g is unique, suppose that g is also a greatest common divisor of a and b. Then we have gg and gg, whence g=±g, and since g,g>0, g=g. ∎

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