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|a$, that $d_2|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$?

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.