# 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)$.

-

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.

[merged for preservation from a deleted question]

Hint $\rm\ \ (n,ab)\ =\ (n,nb,ab)\ =\ (n,(n,a)\:b)\ =\ (n,b)\ =\ 1\$ using prior said GCD laws.

Such exercises are easy on applying the basic GCD laws that I mentioned in your prior questions, viz. the associative, commutative, distributive and modular law $\rm\:(a,b+c\:a) = (a,b)\:.$ In fact, to make such proofs more intuitive one can write $\rm\:gcd(a,b)\:$ as $\rm\:a\dot+ b\:$ and then use familar arithmetic laws, e.g. see this proof of the GCD Freshman's Dream $\rm\:(a\:\dot+\: b)^n =\: a^n\: \dot+\: b^n\:.$

NOTE $\$ Also worth emphasis is that not only are proofs using GCD laws more general, they are also more efficient notationally, hence more easily comprehensible. As an example, below is a proof using the GCD laws, followed by a proof using the Bezout identity (from Gerry's answer).

$\begin{eqnarray} \qquad 1&=& &\rm(a\:,\ \ n)\ &\rm (b\:,\ \ n)&=&\rm\:(ab,\ &\rm n\:(a\:,\ &\rm b\:,\ &\rm n))\ \ =\ \ (ab,n) \\ 1&=&\rm &\rm (ar\!\!+\!\!ns)\:&\rm(bt\!\!+\!\!nu)&=&\rm\ \ ab\:(rt)\!\!+\!\!&\rm n\:(aru\!\!+\!\!&\rm bst\!\!+\!\!&\rm nsu)\ \ so\ \ (ab,n)=1 \end{eqnarray}$

Notice how the first proof using GCD laws avoids all the extraneous Bezout variables $\rm\:r,s,t,u\:,\:$ which play no conceptual role but, rather, only serve to obfuscate the true essence of the matter. Further, without such noise obscuring our view, we can immediately see a natural generalization of the GCD-law based proof, namely

$$\rm\ (a,\ b,\ n)\ =\ 1\ \ \Rightarrow\ \ (ab,\:n)\ =\ (a,\ n)\:(b,\ n)$$

This quickly leads to various refinement-based views of unique factorizations, e.g. the Euclid-Euler Four Number Theorem (Vierzahlensatz) or, more generally, Schreier refinement and Riesz interpolation. See also Paul Cohn's excellent 1973 Monthly survey Unique Factorization Domains.

-

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