650: 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

<The previous article in this series | The table of contents of this series | The next article in this series>

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 $\mathrm{\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) $\mathrm{\forall }{p}_j\in S(\mathrm{\exists }{u}_j\in U,\mathrm{\exists }{i}_{j,k}\in I\cap \overline{R/Asc-f}(p_j=u_j{i}_{j,1}...i_{j,l_j}))$
2) $I^{\prime }:={\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}|j\in \{1,...,n\}\}),...,min(\{c_{j,l}|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^{\prime }:={\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}|j\in \{1,...,n\}\}),...,min(\{c_{j,l}|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^{\prime }=\{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^{\prime }$. 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^{\prime }$, $d=q{d}^{\prime }$ for a $q\in R$.

$d^{\prime }=u^{\prime }{i_1^{\prime }}^{c_1^{\prime }}...{i_m^{\prime }}^{c_m^{\prime }}$, where $u^{\prime }\in U$, $i_j^{\prime }\in I\cap \overline{R/Asc-f}$, and $1\le c_k^{\prime }$, 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}^{\prime }=q_j{u}^{\prime }{i_1^{\prime }}^{c_1^{\prime }}...{i_m^{\prime }}^{c_m^{\prime }}$ and the factorizations are unique with only the leeway of orders, for each $i_s^{\prime }$, $i_s^{\prime }=i_k$ and $c_s^{\prime }\le c_{j,k}$. So, $c_s^{\prime }\le m_k=min(\{c_{j,k}|j\in \{1,...,n\}\})$. Reordering $\{i_1^{\prime },...,i_m^{\prime }\}\cup \{i_1,...,i_l\}$ as $(i_1,...,i_l)$, $d^{\prime }=u^{\prime }{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^{\prime -1}{u}^{\prime }{i}_1^{m_1-c_1^{″}}{i}_1^{c_1^{″}}...i_l^{m_l-c_l^{″}}{i}_l^{c_l^{″}}=u^{\prime -1}{i}_1^{m_1-c_1^{″}}...i_l^{m_l-c_l^{″}}{u}^{\prime }{i}_1^{c_1^{″}}...i_l^{c_l^{″}}=q{d}^{\prime }$, where $q=u^{\prime -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.

---

References

<The previous article in this series | The table of contents of this series | The next article in this series>