Writing and improving basic divisibility proofs in UFD. (some examples)

Question

I'm just learning about UFDs and have many (about 10) properties about divisibility to prove. Not having access to usual tools for these proofs in numbers (like Bezouts ID) is proving very challengeing. It seems Unique Factorization Theorem and the rimness of irreducible are the only tools I have. I have some examples of what I have done so far and I think they are more or less correct (save probably some technical errors). They just seem terribly long and convoluted for such simple statements. My questions are:

1. is this even close to the right approach?
2. how can I clean them up?

Here is some of what I've done: (For what follows; $u_1...u_n$, $v_1...v_m$, $w_1...w_p$ are prime factorizations for $a,b,c$ respectively. $r$ will always denote a unit in $R$.)

Show: If c|ab and gcd(a, c) = 1 then c|b.

Since $u_1...u_n|a(w_1...w_p)$ then $u_i|a(w_1...w_p)$. Since no $u_i$ can divide $a$(else $u_i$ would be a factor of $gcd(a,b)$) we must have $u_i|w_j$ for some $j$ and every $0<i\leq n$ by primness of irreducible elements. After possibly reindexing we have $$b=w_1...w_n=(r_1u_1)(r_2u_2)...(r_nu_n)w_{(n-m+1)}...w_m=c(r_1...r_{n})w_{n-m+1}...w_m.$$ for some set of units $\{r_1...r_n\}$. This proves the claim.

If a|c, b|c, and gcd(a, b) = 1 then ab|c

We know $ab|c^2 \iff (u_1...u_n)(v_1...v_m)|(w_1^2...w_p^2)$. So by the same argument as above; we know that for every $0<i\leq n$ and $0<j\leq m$ we have $u_i|w_k$ for some $0<k\leq p$ and $v_j|w_{k'}$ for some $0<k'\leq p$. Further; for no fixed $w \in \{w_1...w_p\}$ can we whave $u_i|w$ and $v_j|w$ (else $u_i$ and $v_j$ would be associated, violating $gcd(a,b)=1$). Let So after possibly reindexing we have: $$c=w_1...w_p=(u_1r_1...r_nu_n)(r'_1v_1...r'_mv_m)W=ab(r_1...r_n)(r'_1...r'_n)W$$ Where $W$ is some string of $w_i$'s.

If gcd(a, c) = 1 = gcd(b, c) then gcd(ab, c) = 1.

We factor a,b,c into irreducible elements. $a=u_1u_2...u_k$, $b=v_1v_2...v_n$, $c=w_1w_2...w_m$. Then $ab=u_1...u_kv_1...v_n$. Since both $U=\{u_1,...u_k\}$ and $V=\{v_1,....v_n\}$ are disjoint from $W=\{w_1...w_m\}$, we have $U \bigcup V$ disjoint from $W$ which proves the claim.

Answer 1

The proofs seem to be going in the right direction, however there is some considerable improvement that can be made. What is important to realise in this context is that all the propositions you have stated and given proofs for depend exclusively on the existence of a (close attention to be payed to the indefinite article, for one cannot in general speak of a canonically defined object) greatest common divisor for any given pair of elements. In other words, your proofs can be adapted (and presented in a very concise form) in any so-called GCD integral domain, a particular subclass of these being the unique factorisation domains.

1. To give a brief justification for the above statement, consider a UFD $A$. One proves (without much difficulty) that the irreducible elements of $A$ coincide with the nonzero primes. Fixing a complete and independent system of representatives $P$ for the (equivalence) relation of divisibility association on the set of all irreducibles, one easily obtains a canonical isomorphism of monoids: $$A^{\times} \approx \mathrm{U}(A) \times \mathbb{N}^{(P)} \quad (\mathbf{Mon}),$$ where $A^{\times}\colon=A \setminus \{0_A\}$, $\mathrm{U}(A)$ denotes the group of units of $A$ and $\mathbb{N}^{(X)}$ is the free commutative monoid on set $X$. Agrreing to call the above isomorphism $\varphi$ and to denote by $p \colon \mathrm{U}(A) \times \mathbb{N}^{(P)} \to \mathbb{N}^{(P)}$ the canonical projection onto the second factor, it becomes clear that the relation of divisibility on the submonoid $A^{\times} \leqslant_{\mathrm{Mon}} A$ is none other than the preorder obtained by pulling back the direct product order on $\mathbb{N}^{(P)}$ via $p \circ \varphi$, in other words $x|y \Leftrightarrow p(\varphi(x)) \leqslant p(\varphi(y))$ for any $x, y \in A^{\times}$. Equipped with this direct product order say $\Pi$ it is easy to see that $\left(\mathbb{N}^{(P)}, \Pi\right)$ is a lower-bounded distributive lattice, so any two elements $\lambda, \mu \in \mathbb{N}^{(P)}$ will have an infimum given by $\lambda \wedge \mu=\left(\min\{\lambda_t, \mu_t\}\right)_{t \in P}$. Since $p \circ \varphi$ is clearly surjective, given $x, y \in A^{\times}$ we set $\lambda\colon=p(\varphi(x))$, $\mu\colon=p(\varphi(y))$ respectively $\nu\colon=\lambda \wedge \mu$ and we conclude that any $z \in \left(p \circ \varphi\right)^{-1}[\{\nu\}]$ is a greatest common divisor of $x$ and $y$.
2. We thus focus on the more general class of GCD integral domains. I trust that you will make use of this remark in order to improve your standards of syntactical&semantic rigour, so may I point out that there is a very unpleasant element of sloppiness in employing egalitarian notation for the g.c.d of two elements (i.e. using a syntax of the kind $\mathrm{gcd}(x, y)=...$), since in general there is no specific and unique g.c.d of a given pair $(x, y)$ but an entire collection of such objects, all of which are mutually associated. This is so due to the fact that in general the divisibility relation on an integral domain $A$ is only a preorder, whose associated equivalence relation -- the so-called relation of divisibility association -- is none other than the relation of conjugation under the natural action by multiplication of the group of units $\mathrm{U}(A)$ on $A$.
3. Let us though make the essential observation that this lack of antisymmetry of the divisibility preorder can in a sense be remedied by passing down to the quotient. Restricting ourselves to the multiplicative submonoid $A^{\times}$, we know by hypothesis that it is a cancellable commutative monoid (in general, in a monoid $M$ element $x \in M$ is called left-cancellable if the set endomorphism $\gamma_x \colon M \to M$ given by left multiplication with $x$ is injective, and similar definitions apply to right respectively bilaterally cancellable elements; $M$ itself is said to be left/right/bilaterally cancellable if all its elements are left/right/bilaterally cancellable). Let us then turn to an even more general approach, where we consider a commutative cancellable monoid $M$. It is easy to see (by virtue of commutativity) that the conjugation under the action by multiplication of $\mathrm{U}(M)$ on $M$ is actually a congruence on $M$, so we can therefore form the quotient monoid $N\colon=M/\mathrm{U}(M)$. Without difficulty one can prove that $N$ remains a commutative cancellable monoid whose group of units $\mathrm{U}(N)=\{1_N\}$ is furthermore trivial. This entails the fact that the divisibility relation on $N$ is actually an order relation, and it is straightforward that any statement about divisibility in $M$ will have a corresponding equivalent statement of divisibility in $N$, with the mention that what in $M$ is merely a divisibility association becomes in $N$ an actual equality. In particular, $M$ is a so-called GCD monoid (i.e. one in which any pair of elements $x, y \in M$ admits at least a greatest common divisor) if and only if $N$ is an inferior semilattice when ordered by divisibility.
4. With the above preliminaries in mind, we thus realise it is natural to consider the simplified context of a commutative cancellable monoid $M$ with trivial group of units (so that once again divisibility is an order and not merely a preorder), which is at the same time an inferior semilattice with respect to divisibility. We are going to refer to this species as strict GCD monoids. In accordance with the general customs, we will denote the infimum of any set $\{x, y\} \subseteq M$ by $(x; y)$ - none other than the greatest common divisor of the two elements (the semicolon serves to avoid any confusion between our chosen g.c.d notation and the traditional syntax for ordered pairs).

We begin with:

The Fundamental Proposition of GCD Monoids. Let $M$ be a strict GCD monoid and $x, y, t \in M$. We then have the equality $(xt; yt)=(x; y)t$.

Proof. Let us begin by remarking that for any $s \in M$ the set endomorphism $\gamma_s \colon M \to M$ given by $\gamma_s(x)=sx$ is an order embedding with respect to divisibility, in other words that $x|y \Leftrightarrow sx|sy$ for any elements $x, y \in M$. Indeed, $x|y$ clearly entails $sx|sy$ and likewise $sx|sy$ entails $sy=tsx=stx$ for a certain $t \in M$ which leads after simplification by $s$ to $y=tx$ hence $x|y$, reasoning valid in any cancellable commutative monoid (this being the general context in which divisibility is introduced). Let us also note that $\min_{D} M=1_M$, in other words the minimum of $M$ with respect to the relation of divisibility $D$ -- which we point out again is an order relation -- is the unity $1_M$. This entails in particular the implication $s|1_M \Rightarrow s=1_M$ for any $s \in M$ (since there are no units apart from the unity itself).

Returning now to our objective, let us write $z\colon=(x; y)$ and $u\colon=(xt; yt)$. Since $z|x$ and $z|y$ it follows that $tz|tx$ and $tz|ty$ which leads to $tz|u$ by definition of the g.c.d. There exists thus an $s \in M$ such that $u=zst$. From $u|tx$ and $u|ty$ we derive -- after simplifying $t$ -- that $zs|x$ and $zs|y$, whence $zs|z$. Simplification by $z$ entails $s|1_M$ and subsequently $s=1_M$ followed by $u=tz$, Q.E.D. $\Box$

Proposition 1. Let $M$ be a strict GCD monoid and $x, y, t \in M$ such that $(t; x)=1_M$. Then the relation $(t; xy)=(t; y)$ holds.

Proof. Let us begin with the simple observation that if $x, x', y, y' \in M$ are such that $x|x'$ and $y|y'$ then $(x; y)|(x'; y')$. In particular, since $xy|xy$ and $t|ty$ we have $(t; xy)|(ty, xy)=(t; x)y=y$, where the last equality is justified with the Fundamental Proposition. Since by definition we have $(t; xy)|t$, combining with the previous relation we infer $(t; xy)|(t; y)$. The converse relation follows immediately from the starting observation, since obviously $t|t$ and $y|xy$. $\Box$

Corollary 1. If in the strict GCD monoid $M$ the elements $x, y, t \in M$ are such that $t|xy$ and $(t; x)=1_M$ then $t|y$.

Proof. Let us make one more simple observation, namely that for any $u, v \in M$ we have the equivalence $u|v \Leftrightarrow (u; v)=u$. With the given hypotheses we thus have $t=(t; xy)=(t; y)$, the second equality occurring on grounds of the previous proposition, since $(t; x)=1_M$. This means that $t|y$, as per our initial observation. $\Box$

Corollary 2. In a strict GCD monoid $M$, given elements $x, y, z \in M$ such that $x, y|z$ (this being an abbreviated rendition of the conjunction $x|z \wedge y|z$) and $(x; y)=1_M$, it holds that $xy|z$.

Proof. Since $x|z$, there exists $s \in M$ such that $z=sx$. Since $y|sx$ and $(y; x)=1_M$, it follows from corollary 1 that $y|s$. By multiplying with $x$ we obtain that $xy|xs=z$, Q.E.D. $\Box$

Corollary 3. Consider a strict GCD monoid $M$ together with a fixed element $t \in M$ and define the subset $P_t\colon=\{x \in M|\ (x; t)=1_M\}$. Then $P_t \leqslant_{\mathrm{Mon}} M$ is a submonoid.

Proof. It is clear that $1_M \in P_t$. We need to show that $P_t$ is multiplicatively stable (closed under multiplication, in an equivalent rendition). To this end, consider $x, y \in M$ such that $(x; t)=(y; t)=1_M$. Applying proposition 1 with respect to the relation $(t; x)=1_M$ we infer that $(t; xy)=(t; y)=1_M$, which means that along with $x, y \in P_t$ we also have $xy \in P_t$, Q.E.D. $\Box$

Proposition 2. Consider a strict GCD monoid $M$, whose relation of divisibility is $D$. Then $(M, D)$ is also a superior semilattice.

Proof. The claim amounts to showing that any two elements $x, y \in M$ also have a unique least common multiple. Let us set $t\colon=(x; y)$. Since $t|x, y$ (again, an abbreviation of the formal statement $t|x \wedge t|y$), we gather the existence of $r, s \in M$ such that $x=ts$ and $y=tr$. From the Fundamental Proposition we gather that $t=(x; y)=(tr; ts)=t(r; s)$ whence after simplifying by $t$ we obtain $(r; s)=1_M$.

Let us now introduce the element $z\colon=rst \in M$. It is first of all clear that $z=sx=ry$, so $x, y|z$, in other words $z$ is a common multiple of $x$ and $y$. Let us now consider an arbitrary common multiple $u$ of both $x$ and $y$. Since $t|x|u$, by transitivity of divisibility we gather the existence of $v \in M$ such that $u=tv$. From the relations $x=tr|tv$ respectively $y=ts|tv$ we infer – after simplifying by $t$ – that $r, s|v$. Since we have argued above that $r$ and $s$ are relatively prime, corollary 2 entails $rs|v$, which subsequently leads to $z=trs|tv=u$. This means that $z$ divides any common multiple, thus qualifying as the supremum of $\{x, y\}$ with respect to $D$.

Agreeing to denote the least common multiple by $[x; y]\colon=\sup_D \{x, y\}$, let us remark the relation $[x; y](x; y)=xy$. Indeed, in the above notation we have $[x; y](x; y)=zt=rst^2=(rt)(st)=xy$. $\Box$

This concludes our brief introduction to the general theory of (strict) GCD monoids. The term “strict GCD monoid” is not standard terminology, but rather an abbreviation that I felt the need to introduce ad-hoc for convenience.