Difference between revisions of "Euclidean domain"

(Formal definition/examples)
(Proof that a Euclidean domain is a PID)
 
Line 9: Line 9:
 
* The ring of [[Gaussian integers]] <math>\mathbb Z[i]</math> with norm given by <math>N(a+bi) = a^2+b^2</math>.
 
* The ring of [[Gaussian integers]] <math>\mathbb Z[i]</math> with norm given by <math>N(a+bi) = a^2+b^2</math>.
 
* The [[polynomial ring|ring of polynomials]] <math>F[x]</math> over any [[field]] <math>F</math> with norm given by <math>N(p) = \deg p</math>.
 
* The [[polynomial ring|ring of polynomials]] <math>F[x]</math> over any [[field]] <math>F</math> with norm given by <math>N(p) = \deg p</math>.
 +
 +
It can be easily shown through [[infinite descent]] that any Euclidian domain is also a [[principal ideal domain]]. Indeed, let <math>I</math> be any [[ideal]] of a Euclidean domain <math>R</math> and take some <math>a\in I</math> with minimal norm. We claim that <math>I=(a)</math>. Clearly <math>(a)\subseteq I</math>, because <math>I</math> is an ideal. Now assume <math>(a)\ne I</math> and consider any <math>b\in I\setminus (a)</math>. Applying the division algorithm we get that there are <math>q,r\in R</math> such that <math>b=aq+r</math> with <math>N(r)<N(a)</math> (we cannot have <math>r=0</math> as <math>b\not\in (a)</math>). But now as <math>I</math> is an ideal, and <math>a,b\in I</math>, we must have <math>r=b-aq\in I</math>, contradicting the minimality of <math>a</math>. Hence <math>I=(a)</math> and <math>R</math> is indeed a principle ideal domain.
  
 
==See also==
 
==See also==

Latest revision as of 15:28, 22 August 2009

A Euclidean domain (or Euclidean ring) is a type of ring in which the Euclidean algorithm can be used.

Formally we say that a ring $R$ is a Euclidean domain if:

  • It is an integral domain.
  • There a function $N:R\setminus\{0\}\to \mathbb Z_{\ge0}$ called a Norm such that for all nonzero $a,b\in R$ there are $q,r\in R$ such that $a = bq+r$ and either $N(r)<N(b)$ or $r=0$.

Some common examples of Euclidean domains are:

It can be easily shown through infinite descent that any Euclidian domain is also a principal ideal domain. Indeed, let $I$ be any ideal of a Euclidean domain $R$ and take some $a\in I$ with minimal norm. We claim that $I=(a)$. Clearly $(a)\subseteq I$, because $I$ is an ideal. Now assume $(a)\ne I$ and consider any $b\in I\setminus (a)$. Applying the division algorithm we get that there are $q,r\in R$ such that $b=aq+r$ with $N(r)<N(a)$ (we cannot have $r=0$ as $b\not\in (a)$). But now as $I$ is an ideal, and $a,b\in I$, we must have $r=b-aq\in I$, contradicting the minimality of $a$. Hence $I=(a)$ and $R$ is indeed a principle ideal domain.

See also

This article is a stub. Help us out by expanding it.