3
$\begingroup$

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?

Thank you in advance for your help.

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Milo Brandt Sep 14 at 2:20
  • $\begingroup$ @Milo I reverted the question to its original state. $\endgroup$ – LBJFS Sep 14 at 2:24
  • 1
    $\begingroup$ @LBJFS I updated your remark so it peacefully coexists with prior answers (else future answerers might waste their time). $\endgroup$ – Bill Dubuque Sep 14 at 2:30
  • $\begingroup$ @Bill Thank you very much for your help. Now it looks better. $\endgroup$ – LBJFS Sep 14 at 2:31
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ We used basic gcd laws (associative, commutative, distributive) $\endgroup$ – Bill Dubuque Sep 14 at 2:19
  • $\begingroup$ 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 $\endgroup$ – LBJFS Sep 14 at 4:08
  • $\begingroup$ @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)$ $\ \ \ $ $\endgroup$ – Bill Dubuque Sep 14 at 12:50
  • 1
    $\begingroup$ @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. $\endgroup$ – Bill Dubuque Sep 14 at 16:54
  • 1
    $\begingroup$ @LBJFS "the prior" means "my prior" comment. If you tell me what is not clear I can elaborate. $\endgroup$ – Bill Dubuque Sep 14 at 17:03
3
$\begingroup$

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

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 :) $\endgroup$ – LBJFS Sep 14 at 2:04
  • 1
    $\begingroup$ @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. $\endgroup$ – John Omielan Sep 14 at 2:07
  • $\begingroup$ 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. $\endgroup$ – LBJFS Sep 14 at 2:11

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.