nLab greatest common divisor

Redirected from "greatest common divisors".
Contents

Contents

Idea

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.

Remarks

In the natural numbers

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.

One could equivalently equip the natural numbers with a function gcd:×\gcd:\mathbb{N} \times \mathbb{N} \to \mathbb{N} which satisfies the two conditions:

  • gcd(a,b)|a\gcd(a, b)|a and gcd(a,b)|b\gcd(a, b)|b;

  • if c|ac|a and c|bc|b, then c|gcd(a,b)c|\gcd(a, b).

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

or

  • if c|ac|a and c|bc|b, then cgcd(a,b)c \leq \gcd(a, b).

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 or Bézout domain 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.

In the integers

In the set of integers, the greatest common divisor only results in a prelattice rather than a lattice, because the divisibility relation is only a preorder rather than a partial order, due to the fact that there is more than one element of the group of units of the integers.

References

Last revised on February 27, 2024 at 05:59:55. See the history of this page for a list of all contributions to it.