Difference between revisions of "Unique factorization domain"
(Definition) |
(Proof that PID=>UFD) |
||
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>. | * <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>. | * 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}} | {{stub}} | ||
[[Category:Ring theory]] | [[Category:Ring theory]] |
Latest revision as of 23: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 is a unique factorization domain if for any nonzero element which is not a unit:
- can be written in the form where are (not necessarily distinct) irreducible elements in .
- This representation is unique up to units and reordering, that is if where and are all irreducibles then and there is some permutation of such that for each there is a unit such that .
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, (so in this sense, this result is a generalization of the fundamental theorem of arithmetic)
- The Gaussian integers,
- The polynomial ring over any field .
Proof
First we note that in any principal ideal domain, , 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 be irreducible. Then as is a principal ideal domain, must be a maximal ideal. But now in a commutative ring with unity maximal ideals are prime. Thus is prime, and hence is prime.
Now let be any principal domain. First we shall show that any nonzero non-unit in can be factored into irreducibles. Assume that this is not the case. Then let be the set of all non-units in which cannot be written as a product of irreducibles. Consider any . Clearly itself cannot be irreducible, so we may write for some nonzero , neither of which are units. Now if neither nor is in , then both and can be written as a product of irreducibles, and hence so can . This is a contradiction, so at least one of and must be in . WLOG let this be . Now , so and also as is not a unit. Thus and we have proved the following proposition:
- If then there is some element such that .
So now we can construct a sequence of elements of such that (simply let ). But now as is a principal ideal domain, and hence Noetherian, this contradicts the ascending chain condition and is therefore impossible. Thus every element of can indeed be written as the product of irreducibles.
It now remains to show that such representations are unique. For any nonzero , let be the smallest integer such that can be written as the product of irreducibles (this is guaranteed to exist by the previous work). We proceed by strong induction on .
If then is a unit. So now assume that has some other factorization (clearly or this factorization would not be different from the factorization ). Let (or if ). Then we have , which implies that is a unit, a contradiction. So the satement is true for .
Now assume that we have unique factorization for any with . Consider some with . Assume that for irreducibles and (note that by the definition of , ). Now as is irreducible by the above note it must also be prime. Hence as we must have for some . Renumbering the 's if necessary, we may assume WLOG that . So now , and so for some . But is irreducible and is not a unit, so must be a unit. Plugging this back into our expressions for , we get: Now as is an integral domain we get . Letting we get , so by the inductive hypothesis (since is clearly irreducible) there is a unique factorization for . Thus and there is a permutation of and units such that: Combining this with the fact that proves that the representation of is unique and finishes the induction.
Therefore factorization into irreducibles in is unique, and therefore is a unique factorization domain.
This article is a stub. Help us out by expanding it.