# GCD property: $b\mid ac$ implies $b\mid (a,b)(b,c)$

The following is a very simple statement I want to prove:

If $$a,b,c$$ are non-zero integers, then $$b\mid ac$$ implies $$b\mid (a,b)(b,c)$$

Here $$(a,b),[a,b]$$ denote the greatest common divisor and the least common multiple between $$a,b$$, respectively. The symbol $$\mid$$ means divisibility.

Attempt: $$a,b,c\mid ac$$ implies $$[a,b]\mid ac, [b,c]\mid ac$$. Then $$ac=t\frac{ab}{(a,b)}=u\frac{bc}{(b,c)}$$ for some integers $$t,u$$.

Now, it follows that $$(a,b)c=tb, (b,c)a=ub$$. Multiplying we get $$(a,b)(b,c)ac=tub^2$$.

Since $$b\mid ac$$, it follows the existence of an integer $$q$$ s.t. $$ac=bq$$, so that $$(a,b)(b,c)bq=tub^2$$. Clearly $$(a,b)(b,c)q=tub$$.

Here I stuck. Can I argue something more or should I follow a different strategy?

Update I would like to avoid Bezout identity, whenever possible, because I'm interested in applications to GCD domains, where a Bezout identity does not always hold. Some answers using Bezout were posted before this update.

• You shouldn't change a question after it has received answers: it seems like you have a separate question in mind that you haven't explicitly asked: whether this property holds in GCD domains. It'd be far better to ask this as a new question, rather than to try to chase after that with edits - the best thing to do would be to revert this question to its original state and to ask a new question. – Milo Brandt Sep 14 at 2:20
• @Milo I reverted the question to its original state. – LBJFS Sep 14 at 2:24
• @LBJFS I updated your remark so it peacefully coexists with prior answers (else future answerers might waste their time). – Bill Dubuque Sep 14 at 2:30
• @Bill Thank you very much for your help. Now it looks better. – LBJFS Sep 14 at 2:31

$$(b,a)(b,c)= ((b,a)b,(b,a)c) = (bb,ab,bc,ac) = b(b,a,c,ac/b)$$

• We used basic gcd laws (associative, commutative, distributive) – Bill Dubuque Sep 14 at 2:19
• Just curiosity, but do you see a way to prove the statement along the argument I sketched in the question? I ask because I have the feeling the reasoning is not far from the solution, but I don't see how to procede – LBJFS Sep 14 at 4:08
• @LBJFS e.g. $\,(a,b)bc/[b,c] = \color{#c00}b\,(ac,bc)/[b,c],\$ & $\ b,c\mid ac,bc\,\Rightarrow\, [b,c]\mid (ac,bc)$ $\ \ \$ – Bill Dubuque Sep 14 at 12:50
• @LBJFS No the prior comment is a complete proof. It uses $\,b,c\mid d,e\iff [b,c]\mid d,e\iff [b,c]\mid (d,e)\,$ by lcm & gcd universal properties, and also that $\, (b,c)[b,c] = bc.\$ That's all. – Bill Dubuque Sep 14 at 16:54
• @LBJFS "the prior" means "my prior" comment. If you tell me what is not clear I can elaborate. – Bill Dubuque Sep 14 at 17:03

Offering a different strategy (using Bezout).

Let $$d_1:=\gcd(a,b)$$ and $$d_2:=\gcd(b,c)$$. Write $$ac=bk$$, $$d_1=au+bv$$, and $$d_2=bx+cy$$ for $$k,u,v,x,y\in\mathbb Z$$. We have \begin{align}d_1d_2&=(au+bv)(bx+cy)\\&=abuv+(ac)uy+b^2vx+bcvy\\&=b(auv)+(bk)uy+b(bvx)+b(cvy)\\&=b(auv+kuy+bvx+cvy)\end{align} and thus $$b\mid d_1d_2$$.

• Remark that this proof is a special case of the more general gcd-based proof in my answer . – Bill Dubuque Sep 25 at 14:15

By Bezout: $$(a,b)=ak+bl$$ and $$(b,c)=bm+cn$$, so $$(a,b)(b,c)=b\cdot \text{something} + ackn$$, so if $$b$$ divides $$ac$$, it also divides LHS

You can write $$(a,b)$$ and $$(b,c)$$ as an intenger linear combination

$$(a,b) = sa + tb$$ and $$(b,c) = kb + qc$$ for some $$s,t,q,k \in \mathbb{Z}$$

Then, $$(a,b)\cdot (b,c) = sakb +sacq + tbkb + tbqc = b(ask + tbk + tqc) + acsq$$

But we have that $$b|ac$$ then $$ac = bg$$ for some $$g \in \mathbb{Z}$$

So we have that $$(a,b)\cdot (b.c) = b(ask + tbk + tqc) + bgsq = b(ask + tbk + tqc + gsq)$$

Thus $$b|(a,b)(b,c)$$

Here's a proof which uses the Fundamental Theorem of Arithmetic instead of the Bezout Identity, in case that holds in the places you are considering where Bezout does not. Among $$a$$, $$b$$ and $$c$$, there are $$n$$ prime factors, $$p_1$$ to $$p_n$$, for some $$n \ge 0$$. Also, have

$$a = \prod_{i=1}^{n} p_i^{a_i}, \; a_i \ge 0 \tag{1}\label{eq1}$$

$$b = \prod_{i=1}^{n} p_i^{b_i}, \; b_i \ge 0 \tag{2}\label{eq2}$$

$$c = \prod_{i=1}^{n} p_i^{c_i}, \; c_i \ge 0 \tag{3}\label{eq3}$$

Thus,

$$b \mid ac \text{ means } a_i + c_i \ge b_i \text{ for } 1 \le i \le n \tag{4}\label{eq4}$$

Also, you have

$$(a,b)(b,c) = \left(\prod_{i=1}^n p_i^{\min(a_i,b_i)}\right)\left(\prod_{i=1}^n p_i^{\min(b_i,c_i)}\right) = \prod_{i=1}^n p_i^{\min(a_i,b_i) + \min(b_i,c_i)} \tag{5}\label{eq5}$$

Now, for each $$i$$, if $$\min(a_i,b_i) = b_i$$ or $$\min(b_i,c_i) = b_i$$, then their sum would be $$\ge b_i$$. If, instead, $$\min(a_i,b_i) = a_i$$ and $$\min(b_i,c_i) = c_i$$, then their sum of $$a_i + c_i \ge b_i$$. Thus, in all cases, the exponent for $$p_i$$ in \eqref{eq5} is at least $$b_i$$, meaning $$b$$ divides it, i.e.,

$$b \mid (a,b)(b,c) \tag{6}\label{eq6}$$

• Thank you, but this is not what I'm looking for. The main problem with it is that it uses a property which is much stronger than divisibility, so this argument cannot be carried out over GCD domains. Anyway, Thank you :) – LBJFS Sep 14 at 2:04
• @LBJFS You're welcome. I'm not familiar with GCD domains, so I wasn't sure if this would help, but I thought at the minimum it would provide an alternate solution method for the case of integers. – John Omielan Sep 14 at 2:07
• Of course, you are absolutely right! Essentially, your argument can be arranged to show that every UFD is a GCD domain, so this answer meaningful. – LBJFS Sep 14 at 2:11