description/proof of for unique factorization domain, method of getting greatest common divisors of finite subset by factorizing each element of subset with representatives set of associates quotient set
Topics
About: ring
The table of contents of this article
- Starting Context
- Target Context
- Orientation
- Main Body
- 1: Structured Description
- 2: Natural Language Description
- 3: Proof
Starting Context
- The reader knows a definition of unique factorization domain.
- The reader knows a definition of greatest common divisors of subset of commutative ring.
- The reader knows a definition of associates of element of commutative ring.
- The reader knows a definition of representatives set of quotient set.
- The reader admits the proposition that for any integral domain and any subset, if the greatest common divisors of the subset exist, they are the associates of a greatest common divisor.
Target Context
- The reader will have a description and a proof of the proposition that for any unique factorization domain, the method of getting the greatest common divisors of any finite subset by factorizing each element of the subset with the representatives set of the associates quotient set works.
Orientation
There is a list of definitions discussed so far in this site.
There is a list of propositions discussed so far in this site.
Main Body
1: Structured Description
Here is the rules of Structured Description.
Entities:
\(R\): \(\in \{\text{ the unique factorization domains }\}\)
\(U\): \(= \{\text{ the units of } R\}\)
\(I\): \(= \{\text{ the irreducible elements of } R\}\)
\(R / Asc\): \(= \text{ the quotient set by the associates equivalence relation }\)
\(f\): \(: R / Asc \to R\) such that \(\forall p \in R / Asc, f (p) \in p\)
\(\overline{R / Asc - f}\): \(= \text{ the representatives set of } R / Asc \text{ by } f\)
\(S\): \(= \{p_1, ..., p_n\} \in \{\text{ the finite subsets of } R\}\)
\(gcd (S)\):
//
Statements:
\(gcd (S)\) can be gotten in these steps:
1) \(\forall p_j \in S (\exists u_j \in U, \exists i_{j, k} \in I \cap \overline{R / Asc - f} (p_j = u_j i_{j, 1} ... i_{j, l_j}))\)
2) \(I' := \cup_{j \in \{1, ..., n\}} \{i_{j, 1} ... i_{j, l_j}\} = \{i_1, ..., i_l\}\)
3) \(p_j = u_j i_1^{c_{j, 1}} ... i_l^{c_{j, l}}\) where \(0 \le c_{j, k}\)
4) \((m_1, ..., m_l) = (min (\{c_{j, 1} \vert j \in \{1, ..., n\}\}), ..., min (\{c_{j, l} \vert j \in \{1, ..., n\}\}))\)
5) \(gcd (S) = Asc (i_1^{m_1} ... i_l^{m_l})\).
//
2: Natural Language Description
For any unique factorization domain, \(R\), the set of the units of \(R\), \(U\), the set of the irreducible elements of \(R\), \(I\), the quotient set by the associates equivalence relation, \(R / Asc\), any map, \(f: R / Asc \to R\), such that for each \(p \in R / Asc\), \(f (p) \in p\), the representatives set of \(R / Asc\) by \(f\), \(\overline{R / Asc - f}\), and any finite subset, \(S = \{p_1, ..., p_n\} \subseteq R\), the greatest common divisors, \(gcd (S)\), can be gotten in these steps: 1) express each \(p_j \in S\) as \(p_j = u_j i_{j, 1} ... i_{j, l_j}\) where \(u_j \in U\) and \(i_{j, k} \in I\cap \overline{R / Asc - f}\); 2) define \(I' := \cup_{j \in \{1, ..., n\}} \{i_{j, 1} ... i_{j, l_j}\} = \{i_1, ..., i_l\}\); 3) express each \(p_j\) as \(p_j = u_j i_1^{c_{j, 1}} ... i_l^{c_{j, l}}\) where \(0 \le c_{j, k}\); 4) define \((m_1, ..., m_l) = (min (\{c_{j, 1} \vert j \in \{1, ..., n\}\}), ..., min (\{c_{j, l} \vert j \in \{1, ..., n\}\}))\); 5) \(gcd (S) = Asc (i_1^{m_1} ... i_l^{m_l})\).
3: Proof
As \(R\) is a unique factorization domain, \(p_j\) is indeed expressed as \(p_j = u_j i_{j, 1} ... i_{j, l_j}\). That is determined uniquely with only the leeway of orders of the irreducible elements: as \(i_{j, k}\) is chosen from \(\overline{R / Asc - f}\), there is no leeway of choosing another element of \(Asc (i_{j, k})\).
The elements of \(I' = \{i_1, ..., i_l\}\) are from distinct associates equivalence classes.
The expression, \(p_j = u_j i_1^{c_{j, 1}} ... i_l^{c_{j, l}}\), is completely unique, because the order is specified by indexing the elements of \(I'\). When \(i_k\) does not really appear there, \(c_{j, k} = 0\).
\((m_1, ..., m_l)\) is uniquely determined.
\(gcd (S) = Asc (i_1^{m_1} ... i_l^{m_l})\) is uniquely determined.
Let us see that \(Asc (i_1^{m_1} ... i_l^{m_l})\) is indeed \(gcd (S)\).
Let us see that \(d := i_1^{m_1} ... i_l^{m_l}\) is a common divisor.
\(p_j = u_j i_1^{c_{j, 1}} ... i_l^{c_{j, l}} = u_j i_1^{c_{j, 1} - m_1} i_1^{m_1} ... i_l^{c_{j, l} - m_l} i_l^{m_l}\), where \(0 \le c_{j, k} - m_k\), \(= u_j i_1^{c_{j, 1} - m_1} ... i_l^{c_{j, l} - m_l} i_1^{m_1} ... i_l^{m_l} = u_j i_1^{c_{j, 1} - m_1} ... i_l^{c_{j, l} - m_l} d\), where \(u_j i_1^{c_{j, 1} - m_1} ... i_l^{c_{j, l} - m_l} \in R\).
Let us see that for each common divisor, \(d'\), \(d = q d'\) for a \(q \in R\).
\(d' = u' {i'_1}^{c'_1} ... {i'_m}^{c'_m}\), where \(u' \in U\), \(i'_j \in I \cap \overline{R / Asc - f}\), and \(1 \le c'_k\), which is unique with only the leeway of orders of the irreducible elements.
As \(p_j = u_j i_1^{c_{j, 1}} ... i_l^{c_{j, l}} = q_j d' = q_j u' {i'_1}^{c'_1} ... {i'_m}^{c'_m}\) and the factorizations are unique with only the leeway of orders, for each \(i'_s\), \(i'_s = i_k\) and \(c'_s \le c_{j, k}\). So, \(c'_s \le m_k = min (\{c_{j, k} \vert j \in \{1, ..., n\}\})\). Reordering \(\{i'_1, ..., i'_m\} \cup \{i_1, ..., i_l\}\) as \((i_1, ..., i_l)\), \(d' = u' i_1^{c''_1} ... i_l^{c''_l}\), where \(c''_j \le m_j\) for each \(j \in \{1, ..., l\}\).
So, \(d = i_1^{m_1} ... i_l^{m_l} = u'^{-1} u' i_1^{m_1 - c''_1} i_1^{c''_1} ... i_l^{m_l - c''_l} i_l^{c''_l} = u'^{-1} i_1^{m_1 - c''_1} ... i_l^{m_l - c''_l} u' i_1^{c''_1} ... i_l^{c''_l} = q d'\), where \(q = u'^{-1} i_1^{m_1 - c''_1} ... i_l^{m_l - c''_l} \in R\).
So, \(d \in gcd (S)\).
\(gcd (S) = Asc (d)\), by the proposition that for any integral domain and any subset, if the greatest common divisors of the subset exist, they are the associates of a greatest common divisor.
