Difference between revisions of "Unique factorization domain"

Latest revision as of 22:05, 23 August 2009

A unique factorization domain is an integral domain in which an analog of the fundamental theorem of arithmetic holds. More precisely an integral domain $R$ is a unique factorization domain if for any nonzero element $r\in R$ which is not a unit:

$r$ can be written in the form $r=p_1p_2\cdots p_n$ where $p_1,p_2,\ldots,p_n$ are (not necessarily distinct) irreducible elements in $R$ .
This representation is unique up to units and reordering, that is if $r = p_1p_2\cdots p_n = q_1q_2\cdots q_m$ where $p_1,p_2,\ldots,p_n$ and $q_1,q_2\ldots,q_m$ are all irreducibles then $m=n$ and there is some permutation $\sigma$ of $\{1,2\ldots,n\}$ such that for each $k$ there is a unit $u_k$ such that $p_k = u_kq_{\sigma(k)}$ .

One of the most significant results about unique factorization domains is that any principal ideal domain (and hence any euclidean domain) is a unique factorization domain. This automatically implies that many well-known rings are unique factorization domains including:

The ring of integers, $\mathbb Z$ (so in this sense, this result is a generalization of the fundamental theorem of arithmetic)
The Gaussian integers, $\mathbb Z[i]$
The polynomial ring $F[x]$ over any field $F$ .

Proof

First we note that in any principal ideal domain, $R$ , the irreducible elements are precisely the prime elements. One implication (that any prime element is irreducible) is known to be true for any integral domain. For the other direction, let $m\in R$ be irreducible. Then as $R$ is a principal ideal domain, $(m)$ must be a maximal ideal. But now in a commutative ring with unity maximal ideals are prime. Thus $(m)$ is prime, and hence $m$ is prime.

Now let $R$ be any principal domain. First we shall show that any nonzero non-unit in $R$ can be factored into irreducibles. Assume that this is not the case. Then let $S\subseteq R$ be the set of all non-units in $R$ which cannot be written as a product of irreducibles. Consider any $r\in S$ . Clearly $r$ itself cannot be irreducible, so we may write $r=ab$ for some nonzero $a,b\in R$ , neither of which are units. Now if neither $a$ nor $b$ is in $S$ , then both $a$ and $b$ can be written as a product of irreducibles, and hence so can $r$ . This is a contradiction, so at least one of $a$ and $b$ must be in $S$ . WLOG let this be $a$ . Now $a|r$ , so $(r)\subseteq (a)$ and also $(r)\ne (a)$ as $b$ is not a unit. Thus $(r)\subset (a)$ and we have proved the following proposition:

If $r\in S$ then there is some element $r'\in S$ such that $(r)\subset (r')$ .

So now we can construct a sequence $r_1,r_2,\ldots$ of elements of $S$ such that $(r_1)\subset (r_2)\subset (r_3) \subset \cdots$ (simply let $r_n = (r_{n-1})'$ ). But now as $R$ is a principal ideal domain, and hence Noetherian, this contradicts the ascending chain condition and is therefore impossible. Thus every element of $R$ can indeed be written as the product of irreducibles.

It now remains to show that such representations are unique. For any nonzero $r\in R$ , let $f(r)$ be the smallest integer $n$ such that $r$ can be written as the product of $n$ irreducibles (this is guaranteed to exist by the previous work). We proceed by strong induction on $f(r)$ .

If $f(r) = 0$ then $r$ is a unit. So now assume that $r$ has some other factorization $r = p_1p_2\cdots p_m$ (clearly $m>0$ or this factorization would not be different from the factorization $r=r$ ). Let $P = p_2\cdots p_m$ (or $P=1$ if $m=1$ ). Then we have $r = p_1P\Rightarrow 1 = p_1(Pr^{-1})$ , which implies that $p_1$ is a unit, a contradiction. So the satement is true for $f(r)=0$ .

Now assume that we have unique factorization for any $r$ with $f(r)<n$ . Consider some $s\in R$ with $f(s)=n$ . Assume that $s = p_1p_2\cdots p_n=q_1q_2\cdots q_m,$ for irreducibles $p_1,p_2,\ldots,p_n$ and $q_1,q_2\ldots,q_m$ (note that by the definition of $f(s)$ , $n\le m$ ). Now as $p_n$ is irreducible by the above note it must also be prime. Hence as $p_n|q_1q_2\cdots q_m$ we must have $p_n|q_k$ for some $k$ . Renumbering the $q_i$ 's if necessary, we may assume WLOG that $k=m$ . So now $p_n|q_m$ , and so $q_m=p_nc$ for some $c\in R$ . But $q_m$ is irreducible and $p_n$ is not a unit, so $c$ must be a unit. Plugging this back into our expressions for $s$ , we get: $s = p_1p_2\cdots p_{n-1}p_n=q_1q_2\cdots q_{m-1}q_m = q_1q_2\cdots q_{m-1}(p_nc) = (q_1c)q_2\cdots q_{m-1}p_n.$ Now as $R$ is an integral domain we get $p_1p_2\cdots p_{n-1}=(cq_1)q_2\cdots q_{m-1}$ . Letting $s' = p_1p_2\cdots p_{n-1}$ we get $f(s')\le n-1$ , so by the inductive hypothesis (since $cq_1$ is clearly irreducible) there is a unique factorization for $s'$ . Thus $m=n$ and there is a permutation $\sigma$ of $\{1,2,\ldots,n-1\}$ and units $u_1,u_2,\ldots,u_{n-1}\in R$ such that: $\begin{align*} q_1 &= (u_1c^{-1}) p_{\sigma(1)}\\ q_2 &= u_2p_{\sigma(2)}\\ &\cdots\\ q_{n-1} &= u_{n-1}p_{\sigma(n-1)}\\ \end{align*}$ Combining this with the fact that $q_n = cp_n$ proves that the representation of $s$ is unique and finishes the induction.

Therefore factorization into irreducibles in $R$ is unique, and therefore $R$ is a unique factorization domain.

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

@@ Line 1: / Line 1: @@
-A '''unique factorization domain''' is an [[integral domain]] in which an analog of the [[fundamental theorem of arithmetic]] holds. More precisely an integral domain <math>R</math> is a unique factorization domain if for any element <math>r\in R</math> which is not a [[unit (ring theory)|unit]]:
+A '''unique factorization domain''' is an [[integral domain]] in which an analog of the [[fundamental theorem of arithmetic]] holds. More precisely an integral domain <math>R</math> is a unique factorization domain if for any nonzero element <math>r\in R</math> which is not a [[unit (ring theory)|unit]]:
 * <math>r</math> can be written in the form <math>r=p_1p_2\cdots p_n</math> where <math>p_1,p_2,\ldots,p_n</math> are (not necessarily distinct) [[irreducible element]]s in <math>R</math>.
 * This representation is unique up to units and reordering, that is if <math>r = p_1p_2\cdots p_n = q_1q_2\cdots q_m</math> where <math>p_1,p_2,\ldots,p_n</math> and <math>q_1,q_2\ldots,q_m</math> are all irreducibles then <math>m=n</math> and there is some [[permutation]] <math>\sigma</math> of <math>\{1,2\ldots,n\}</math> such that for each <math>k</math> there is a unit <math>u_k</math> such that <math>p_k = u_kq_{\sigma(k)}</math>.
+One of the most significant results about unique factorization domains is that any [[principal ideal domain]] (and hence any [[euclidean domain]]) is a unique factorization domain. This automatically implies that many well-known rings are unique factorization domains including:
+* The ring of [[integer]]s, <math>\mathbb Z</math> (so in this sense, this result is a generalization of the fundamental theorem of arithmetic)
+* The [[Gaussian integer]]s, <math>\mathbb Z[i]</math>
+* The [[polynomial ring]] <math>F[x]</math> over any field <math>F</math>.
+==Proof==
+First we note that in any principal ideal domain, <math>R</math>, the [[irreducible element]]s are precisely the [[prime element]]s. One implication (that any prime element is irreducible) is known to be true for any integral domain. For the other direction, let <math>m\in R</math> be irreducible. Then as <math>R</math> is a principal ideal domain, <math>(m)</math> must be a [[maximal ideal]]. But now in a [[commutative ring]] with unity [[maximal ideal]]s are [[prime ideal|prime]]. Thus <math>(m)</math> is prime, and hence <math>m</math> is prime.
+Now let <math>R</math> be any principal domain. First we shall show that any nonzero non-unit in <math>R</math> can be factored into irreducibles. Assume that this is not the case. Then let <math>S\subseteq R</math> be the set of all non-units in <math>R</math> which cannot be written as a product of irreducibles. Consider any <math>r\in S</math>. Clearly <math>r</math> itself cannot be irreducible, so we may write <math>r=ab</math> for some nonzero <math>a,b\in R</math>, neither of which are units. Now if neither <math>a</math> nor <math>b</math> is in <math>S</math>, then both <math>a</math> and <math>b</math> can be written as a product of irreducibles, and hence so can <math>r</math>. This is a contradiction, so at least one of <math>a</math> and <math>b</math> must be in <math>S</math>. WLOG let this be <math>a</math>. Now <math>a|r</math>, so <math>(r)\subseteq (a)</math> and also <math>(r)\ne (a)</math> as <math>b</math> is not a unit. Thus <math>(r)\subset (a)</math> and we have proved the following proposition:
+* If <math>r\in S</math> then there is some element <math>r'\in S</math> such that <math>(r)\subset (r')</math>.
+So now we can construct a sequence <math>r_1,r_2,\ldots</math> of elements of <math>S</math> such that
+<cmath>(r_1)\subset (r_2)\subset (r_3) \subset \cdots</cmath>
+(simply let <math>r_n = (r_{n-1})'</math>). But now as <math>R</math> is a principal ideal domain, and hence [[Noetherian]], this contradicts the [[ascending chain condition]] and is therefore impossible. Thus every element of <math>R</math> can indeed be written as the product of irreducibles.
+It now remains to show that such representations are unique. For any nonzero <math>r\in R</math>, let <math>f(r)</math> be the ''smallest'' integer <math>n</math> such that <math>r</math> can be written as the product of <math>n</math> irreducibles (this is guaranteed to exist by the previous work). We proceed by strong induction on <math>f(r)</math>.
+If <math>f(r) = 0</math> then <math>r</math> is a unit. So now assume that <math>r</math> has some other factorization <math>r = p_1p_2\cdots p_m</math> (clearly <math>m>0</math> or this factorization would not be different from the factorization <math>r=r</math>). Let <math>P = p_2\cdots p_m</math> (or <math>P=1</math> if <math>m=1</math>). Then we have <math>r = p_1P\Rightarrow 1 = p_1(Pr^{-1})</math>, which implies that <math>p_1</math> is a unit, a contradiction. So the satement is true for <math>f(r)=0</math>.
+Now assume that we have unique factorization for any <math>r</math> with <math>f(r)<n</math>. Consider some <math>s\in R</math> with <math>f(s)=n</math>. Assume that <cmath>s = p_1p_2\cdots p_n=q_1q_2\cdots q_m,</cmath> for irreducibles <math>p_1,p_2,\ldots,p_n</math> and <math>q_1,q_2\ldots,q_m</math> (note that by the definition of <math>f(s)</math>, <math>n\le m</math>). Now as <math>p_n</math> is irreducible by the above note it must also be prime. Hence as <math>p_n|q_1q_2\cdots q_m</math> we must have <math>p_n|q_k</math> for some <math>k</math>. Renumbering the <math>q_i</math>'s if necessary, we may assume WLOG that <math>k=m</math>. So now <math>p_n|q_m</math>, and so <math>q_m=p_nc</math> for some <math>c\in R</math>. But <math>q_m</math> is irreducible and <math>p_n</math> is not a unit, so <math>c</math> must be a unit. Plugging this back into our expressions for <math>s</math>, we get:
+<cmath>s = p_1p_2\cdots p_{n-1}p_n=q_1q_2\cdots q_{m-1}q_m = q_1q_2\cdots q_{m-1}(p_nc) = (q_1c)q_2\cdots q_{m-1}p_n.</cmath>
+Now as <math>R</math> is an integral domain we get <math>p_1p_2\cdots p_{n-1}=(cq_1)q_2\cdots q_{m-1}</math>. Letting <math>s' = p_1p_2\cdots p_{n-1}</math> we get <math>f(s')\le n-1</math>, so by the inductive hypothesis (since <math>cq_1</math> is clearly irreducible) there is a unique factorization for <math>s'</math>. Thus <math>m=n</math> and there is a permutation <math>\sigma</math> of <math>\{1,2,\ldots,n-1\}</math> and units <math>u_1,u_2,\ldots,u_{n-1}\in R</math> such that:
+<cmath>
+\begin{align*}
+q_1 &= (u_1c^{-1}) p_{\sigma(1)}\\
+q_2 &= u_2p_{\sigma(2)}\\
+&\cdots\\
+q_{n-1} &= u_{n-1}p_{\sigma(n-1)}\\
+\end{align*}
+</cmath>
+Combining this with the fact that <math>q_n = cp_n</math> proves that the representation of <math>s</math> is unique and finishes the induction.
+Therefore factorization into irreducibles in <math>R</math> is unique, and therefore <math>R</math> is a unique factorization domain.
 {{stub}}
 [[Category:Ring theory]]

Page

Toolbox

Search

Difference between revisions of "Unique factorization domain"

Latest revision as of 22:05, 23 August 2009

Proof