# Basic divisibility fact

I'm trying to prove "the following generalization of Theorem 5 [ Th.5: if $a|bc$ and $(a,b)=1$ then $a | c$ ], which uses the same argument for its proof" (Sierpinski, The Theory of Numbers): if $a$, $b$, and $c$ are integers such that $b | ac$, then $b | (a,b)(b,c)$.

I haven't been able to prove it without any reference to prime numbers (which the author introduces way later), using only divisibility and facts like $(a,b)[a,b]=ab$. Here's what I've done so far:

Let $(a,b)=d_a$, $(b,c)=d_c$, $a=a'd_a$, $c=c'd_c$. Since $b | ac$ and $a | ac$ $\Rightarrow [b,a] | ac$ (this is the argument used in Th5's proof) $\Rightarrow ab/(a,b) | ac \Rightarrow a'b | ac \Rightarrow b | d_a c$. Doing the same for $c$, we get $b | ad_c$. From this we also have $b | (ad_c,d_a c)$.

Thank you for your help.

-

HINT $\ \ \ \rm ad = bc\ \:\Rightarrow\:\ (a,b)\:(a,c)\: =\ (aa,ab,ac,bc)\: =\: a\:(a,b,c,d)\: =\: a\:,\:$ by $\rm\:(a,b) = 1\:.\:$
Thus $\rm\:(a,c) = a\:,\:$ so $\rm\:a\:|\:c\:.\:$ We used only basic GCD laws (distributive, commutative, associative).

Alternatively $\rm\:(a,bc) = (a\:(1,c),bc) = (a,ac,bc) = (a,(a,b)c)\ [\:= (a,c)\quad if\quad (a,b) = 1]$
See here for much more on this proof, esp. on how to view it in analogy with integer arithmetic.

Alternatively, if you know the LCM $\cdot$ GCD law $\rm\ [a,b]\: (a,b)\: =\: ab\$ then, employing this law,

we have $\rm\ \ \: a,b\:|\:bc\ \:\Rightarrow\ \: [a,b]\:|\:bc\ \ \Rightarrow\:\ ab\:|(a,b)\:bc\ \Rightarrow\ a\:|\:(a,b)\:c\:,\$ so $\rm\:a\:|\:c\:$ when $\rm\:(a,b)= 1\:.$

This appears to be the proof that Sierpinski has in mind since his prior proof is merely the special case where $\rm\ \ (a,b)= 1\:,\:$ and it employs the consequent specialization of the above $\$ LCM $\cdot$ GCD $\$ law, explicitly that $\rm\ (a,b) = 1\ \Rightarrow\ [a,b] = ab\:$.

For a proof of the LCM $\cdot$ GCD law simpler than Sierpinski's see the one line universal proof of the Theorem here. Not only is this proof simpler but it is also more general - it works in any domain.

Note also that the result that you seek is a special case of the powerful $\:$ Euler four number theorem (Vierzahlensatz),$\:$ or $\:$ Riesz interpolation, or $\:$ Schreier refinement. For another example of the simplicity of proofs founded upon the fundamental GCD laws (associative, commutative, distributive, and absorptive laws), see my post on the Freshman's Dream $\rm\: (A+B)^n =\: A^n + B^n\$ for GCDs / Ideals, $\:$ if $\rm\: A+B\$ is cancellative. It's advantageous to present gcd proofs using these basic laws (vs. the Bezout linear form) since such proofs will generalize better (e.g. to ideal arithmetic) and, moreover, since these laws are so similar to integer arithmetic, we can reuse are well-honed expertise manipulating expressions obeying said well-known arithmetic laws. For examples see said Freshman's Dream post.

-

Hint: write $(a,b)$ as a linear combination of $a$ and $b$, $(b,c)$ as a linear combination of $b$ and $c$.

-
that works. But I checked his reference and that fact isn't known up to that point, I think he wants an even more 'elementary' proof (not that this fact isn't elementary). –  Weltschmerz Oct 13 '10 at 4:26
@Weltschmerz: Yes, Sierpinski doesn't present the Bezout linear representation of the GCD until much later in Section 10, so the above approach is certainly not known at that point. See my post for one guess as to the method Sierpinski intended. –  Bill Dubuque Oct 13 '10 at 22:39