greatest common divisor




The natural numbers 0,1,2,0, 1, 2, \ldots are partially ordered by the divisibility relation: a|ba|b if b=akb = a k for some natural number kk. This poset is in fact a lattice. The greatest common divisor of a,ba, b is their meet in this lattice.


Spelled out, this means that the greatest common divisor of a,ba, b \in \mathbb{N}, denoted gcd(a,b)\gcd(a, b), is the element dd \in \mathbb{N} uniquely characterized by the following two conditions:

  • d|ad|a and d|bd|b;

  • if c|ac|a and c|bc|b, then c|dc|d.

It is almost but not quite true that “greatest” means greatest with respect to the usual ordering \leq. In particular, 00 is the maximal element with respect to the divisibility ordering, and gcd(0,0)=0\gcd(0, 0) = 0 according to the definition above. However, there is no “greatest” common divisor of 00 with itself if we construe “greatest” in the sense of \leq: every natural number is a common divisor of 00 with itself, and there is no \leq-greatest natural number!

Thus, the convention often seen in textbooks, which replaces the second condition above with

  • if c|ac|a and c|bc|b, then cdc \leq d

is slightly more awkward, and certainly less “pure” (mixing two relations || and \leq). It is also less robust, because the notion of gcdgcd is at bottom an ideal-theoretic notion: the divisibility order on elements of a principal ideal domain is a preorder whose posetal collapse is the collection of ideals, ordered oppositely to inclusion. Thus, in ring-theoretic contexts where there is no sensible notion of \leq, for example in the ring of Gaussian integers, the notion of gcdgcd still makes perfectly good sense if we use the first formulation above, expressed purely in terms of divisibility.

From the point of view of principal ideals in a pid RR, the gcd corresponds to taking their join: (gcd(a,b))=(a)+(b)(\gcd(a, b)) = (a) + (b). Thus the Euclidean algorithm, which applies generally to Euclidean domains RR, is a way of calculating a generator of (a)+(b)(a) + (b) which consists of RR-linear combinations of aa and bb.


Last revised on December 19, 2020 at 15:18:23. See the history of this page for a list of all contributions to it.