Prove general Euclid's Lemma in a UFD using prime factorization I have seen plenty of proofs for this theorem:
In a UFD if $(a,b)=1$ and $a|bc$ then $a|c$.
They mostly use the gcd distributive law e.g. here.
Well I wanted to prove this just by relying on the properties that the UFD had.
My attempt:
Since $a|bc$ then for some $r$ we have $ar=bc$.
Now by the existence, since we know that any non unit element like $a$ can be rewritten as $t_1×....t_n$ where $t_i$ are irreducible, we can do this:
$$p_1^{α_1}...p_n^{α_n} g_1^{ε_1}...g_m^{ε_m} =q_1^{β_1}...q_k^{β_k}h_1^{ψ_1}...h_i^{ψ_i}$$
(Where $p_i$, $g_i$, $q_i$ and $h_i$ are primes.)
By uniqueness the set that is on right should be on left too, Am I right?
But since $(a,b)=1$ then $a$ and $b$ shouldn't share prime elements. Somehow it's like $A$ is a subset of $C$. I can't really manage this but it's becoming like a problem in set theory.
Can you please help me with my own approach??
 A: You're very close. Let's look back at this equation you stated:'
$$
p_1^{α_1}...p_n^{α_n} g_1^{ε_1}...g_m^{ε_m} =q_1^{β_1}...q_k^{β_k}h_1^{ψ_1}...h_i^{ψ_i}
$$
corresponding to $ar=bc$. As you said, because we are in a UFD the set of primes, counted with multiplicity, is the same on both sides (up to units). Furthermore, as $(a,b)=1$ then no $p_i$ can divide $b$. Once again by uniqueness, that means that no $p_i$ can divide $q_j$. In fact, we can go farther and say that no $p_i^{\alpha_i}$ can divide $q_j$. Putting this together, all the $p_i^{\alpha_i}$ must appear in the factorization on the right hand side (up to units). Furthermore, the $p_i^{\alpha_i}$ cannot divide the $q_j$. Thus, up to units, the $p_i^{\alpha_i}$ must each divide some $h_j^{\psi_j}$. Hence, all the prime factors of $a$ counted with multiplicity divide $c$. Hence, $a \mid c$.
A: It has a natural proof by induction on the number $\:\!k\:\!$ of prime factors of $\,a,\,$ using as inductive step Euclid's Lemma (if a prime divides a product then it divides some factor). If $\,k=0\,$ then $\,a\,$ is a unit so $\,a\mid c.\,$ Else $\,a = p\bar a\,$ for a prime $\,p\,$ so $\,p\bar a\mid bc\,\Rightarrow\,p\mid b\,$ or $\,p\mid c,\,$ so $\,\color{#c00}{p\mid c}\,$ by $\,(p,b)=1\,$ by $\,(p\bar a,b)=1$. Cancelling $\,p\,$ from $\,p\bar a\mid bc\Rightarrow \bar a\mid b\,\color{#c00}{c/p},\,$ and $\,(\bar a,b)=1\,$ by $\,(p\bar a,b)=1.\,$ Notice $\,\bar a\,$ has fewer  prime factors than $\,a=p\bar a,\,$ thus $\,\bar a\mid \color{#c00}{c/p}\underset{\textstyle\times\, p}\Rightarrow p\bar a\mid c\ $ (i.e. $\,a\mid c),\,$ by induction.
Exercise $ $ Make explicit all  implicit uses of the existence and uniqueness of prime factorizations that are employed in the proof (necessary to be completely rigorous).
