This site is supported by donations to The OEIS Foundation.

Euclidean domains

From OeisWiki
(Redirected from Euclidean domain)
Jump to: navigation, search

This article is under construction.

Please do not rely on any information it contains.



This article page is a stub, please help by expanding it.

A given ring is a Euclidean domain with respect to some function if for any numbers , if then , and there are always numbers such that with . The norm function is often used, so then if is Euclidean in regards to norm, it is called a norm-Euclidean domain. For example, is a norm-Euclidean domain, as it is Euclidean with respect to the norm function . (See A003174 and A048981).

All Euclidean domains are principal ideal domains, but not all principal ideal domains are Euclidean. For example, of the nine imaginary quadratic integer rings that are principal ideal domains, only five are Euclidean: , , , and .

The Euclidean algorithm to calculate the GCD of two integers in can be adapted and implemented in any Euclidean domain, and it will always execute correctly. In non-Euclidean domains, there may be cases in which the Euclidean algorithm seems to work but there will also be cases in which it doesn't.

Theorem. is a Euclidean domain in regards to the absolute value function. Given any two integers , there are always integers such that and .

Proof. (Euclid) [THIS IS JUST A MATTER OF COPYING EUCLID'S PROOF FROM A MODERN TRANSLATION OF THE ELEMENTS]

For quadratic integer rings that are Euclidean, the Euclidean function is often either the norm (in the case of imaginary rings) or the absolute value of the norm (in the case of real rings).

Domain Euclidean function Domain Euclidean function
Norm
Absolute value of the norm
N/A, not PID nor UFD
Norm
N/A, not PID nor UFD N/A, not PID nor UFD
Norm Absolute value of the norm
N/A, not PID nor UFD
 ???
N/A, not PID nor UFD
Absolute value of the norm
None, though this is a PID
N/A, not PID nor UFD
 ???
 ???
N/A, not PID nor UFD
Absolute value of the norm
N/A, not PID nor UFD
 ???
Absolute value of the norm
N/A, not PID nor UFD
Absolute value of the norm
 ???
N/A, not PID nor UFD
Absolute value of the norm
N/A, not PID nor UFD
None, though this is a PID  ???
N/A, not PID nor UFD  ???
 ???
N/A, not PID nor UFD
 ???
N/A, not PID nor UFD
Absolute value of the norm
N/A, not PID nor UFD
 ???
 ???
 ???
N/A, not PID nor UFD
None, though this is a PID  ???
N/A, not PID nor UFD Absolute value of the norm but with one special adjustment[1]
N/A, not PID nor UFD
 ???
Absolute value of the norm
N/A, not PID nor UFD
  1. For any number divisible by change the multiplicative contribution of that number to the absolute value of the norm from 23 to 26.