transfinite arithmetic, cardinal arithmetic, ordinal arithmetic
prime field, p-adic integer, p-adic rational number, p-adic complex number
arithmetic geometry, function field analogy
The natural numbers are partially ordered by the divisibility relation: if for some natural number . This poset is in fact a lattice. The greatest common divisor of is their meet in this lattice.
Spelled out, this means that the greatest common divisor of , denoted , is the element uniquely characterized by the following two conditions:
and ;
if and , then .
One could equivalently equip the natural numbers with a function which satisfies the two conditions:
and ;
if and , then .
It is almost but not quite true that “greatest” means greatest with respect to the usual ordering . In particular, is the maximal element with respect to the divisibility ordering, and according to the definition above. However, there is no “greatest” common divisor of with itself if we construe “greatest” in the sense of : every natural number is a common divisor of with itself, and there is no -greatest natural number!
Thus, the convention often seen in textbooks, which replaces the second condition above with
or
is slightly more awkward, and certainly less “pure” (mixing two relations and ). It is also less robust, because the notion of 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 , for example in the ring of Gaussian integers, the notion of 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 , the gcd corresponds to taking their join: . Thus the Euclidean algorithm, which applies generally to Euclidean domains , is a way of calculating a generator of which consists of -linear combinations of and .
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.
Last revised on February 27, 2024 at 05:59:55. See the history of this page for a list of all contributions to it.