Divisor of a product of integers is a product of divisors

I read this recently on the web and can't manage to understand it. Not homework -- I haven't done math homework for years.

If $d\mid ab$ then $d=d_1 d_2$, that $d_1\mid a$, that $d_2\mid b$ and, further, if $(a,b)=1$ then $(d_1,d_2)=1$.

I know it's the same question... if $a = a_1 a_2 ... a_n$, why can't $d$ divide some $a_i$ and only $a_i$?

Solution 1:

Hint $ $ by $\, d\mid j,k\color{#c00}\iff d\mid (j,k)\,$ [gcd universal property], and $\,\rm\color{#0a0}{DL} =$ gcd Distributive Law

$\,\ d\mid ab\iff d\mid ab,db \color{#c00}\iff d\mid (ad,db)\overset{\color{#0a0}{\rm D\,L}} = (a,d)b \iff \color{#90f}{d/(a,d)\mid b}$

Hence we conclude $\ d\, =\, (a,d)\, \dfrac{d}{(a,d)} \ $ where $\ (a,d)\mid a,\ $ and $\ \color{#90f}{\dfrac{d}{(a,d)}\mid b},\ $ as sought.

It works fine if $\ d\mid a,\,$ then $\,(a,d)=d\ $ so $\,d/(a,d) = 1,\,$ so $\,d = d\cdot 1\,$ where $\,d\mid a,\ 1\mid b$.

Generalization $ $ The property that is considered in your question may be considered to be a generalization of the prime divisor property from atoms (irreducibles) $\,p\,$ to composites $\,c.\,$

Prime Divisor Property $\quad p\ |\ a\:b\ \Rightarrow\ p\:|\:a\ $ or $\ p\:|\:b\ \ $ [= Euclid's Lemma in $\Bbb Z$]

Primal Divisor Property $\ \ \: c\ |\ a\:b\ \Rightarrow\ c_1\, |\: a\:,\: $ $\ c_2\:|\:b,\ \ c = c_1\:c_2\ $

One easily checks that atoms are primal $\Leftrightarrow$ prime. This leads to various "refinement" views of unique factorizations, e.g. via Schreier refinement and Riesz interpolation, the Euclid-Euler Four Number Theorem (aka Vierzahlensatz), etc, which prove more natural in noncommutative rings - see Paul Cohn's 1973 Monthly survey Unique Factorization Domains.