# implication of a number dividing a product of relatively prime numbers

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|ab$ and $(a,b)=1$, prove that $d=d_1 d_2$, that $d_1|a$, that $d_2|b$, and $(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$?

• It can, but then the other part of $d$ is just 1. Which satisfies $(d1,1)=1$ automatically – amcalde Feb 7 '15 at 4:25
• Look at an example. d=6,a=4,b=3 – voldemort Feb 7 '15 at 4:27
• And another example: $d=6$, $a=12$, $b=5$. – Greg Martin Feb 7 '15 at 4:50

Hint $$\,\ 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 d/(a,d)\mid b$$

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

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

Remark $$\$$ Above we used $$\, d\mid j,k\color{#c00}\iff d\mid (j,k),\,$$ the universal property of the gcd.

Proof $$\ \ (\Leftarrow)\ \ \ d\mid(j,k)\mid j,k.\ \ (\Rightarrow)\ \$$ By Bezout $$\,(j,k) = mj+nk\,$$ so $$\,d\mid j,k\,\Rightarrow\,d\mid (j,k).\,$$

We also used $$\,\rm\color{#0a0}{DL} =$$ the gcd Distributive Law.

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\$$

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 (Vierzahlensatz), etc, which prove more natural in noncommutative rings - see Paul Cohn's 1973 Monthly survey Unique Factorization Domains.

• Thank you. I'm curious about the second item in the equivalence chain in your hint... – QED Feb 8 '15 at 4:14
• @psoft I elaborated on that. – Bill Dubuque Feb 8 '15 at 4:58
• I'm sorry, I just don't understand the notation d|x,y. d divides both x and y? – QED Feb 8 '15 at 14:25
• @psoft Yes $\ d\mid x,y\,$ means $\,d\mid x,\ d\mid y\ \$ – Bill Dubuque Feb 8 '15 at 14:28