Euclidean domains and principal ideals

A Euclidean domain is an integral domain equipped with a nonnegative integer-valued size on nonzero elements such that division by a nonzero element gives a remainder of strictly smaller size, or zero. Some definitions impose additional harmless conditions on the size function; the remainder property is the part needed here. Integers use absolute value, while polynomials over a field use degree. The existence of a Euclidean function does not mean that it is simply the ordinary absolute value in every example.

Repeated division gives a chain of smaller nonzero remainders. A strictly decreasing sequence of nonnegative integers cannot continue forever, so the chain ends. Each division preserves the common divisors of the current pair: a divisor of both the dividend and divisor also divides the remainder, and a divisor of the divisor and remainder also divides the dividend. The last nonzero remainder therefore has precisely the greatest-common-divisor divisibility property.

Every remainder is a linear combination of the previous pair. Back substitution therefore expresses the last nonzero remainder as a combination of the original two inputs. This is a Bézout identity, a certificate that can be verified by one multiplication-and-addition calculation even if the algorithm producing it was long. In a polynomial ring over a field, normalize the greatest common divisor to be monic to choose a standard representative among its unit multiples.

If that greatest common divisor is one, the Bézout identity supplies inverses in a quotient. A relation uf plus vg equals one says that the class of u is an inverse for the class of f modulo g. This is the polynomial analogue of finding inverses modulo an integer. Conversely, a common nonunit divisor prevents such an identity. The certificate is more informative than a numerical declaration that two elements are relatively prime.

Let I be a nonzero ideal in a Euclidean domain. Choose a nonzero element d in I having the smallest possible Euclidean size. Divide an arbitrary a in I by d. The remainder is also in I because it equals a minus a ring multiple of d. A nonzero remainder would have smaller size than d, contradicting minimality. Hence every a in I is a multiple of d, and the ideal is principal.

The zero ideal is already principal, generated by zero. Thus every Euclidean domain is a principal ideal domain, usually abbreviated PID. The converse is not automatic: a theorem guaranteeing single generators need not provide a Euclidean division function. Nor does taking a polynomial ring over a PID generally preserve the PID property. The ring of integer polynomials contains the nonprincipal ideal generated by two and x, so it is not a Euclidean domain either.