# Thread: proof involving least common multiple

1. ## proof involving least common multiple

For every choice of non zero integers a,b,c, the integer lcm[a,c] divides
the integer lcm[a,b] * lcm[b,c] / b.

I was thinking of letting a=p/q, b=r/s, c=t/u. Then, somehow, the integer lcm[a,b] * lcm[b,c] / b will factor out an lcm[a,c], but I am not sure how to prove it that way.

2. I thought about it, and this is what I got so far:

lcm[a,b] = ab/(a,b), and so on.

(a,c)=ax+cy
(a,b)=ax+by
(b,c)=bx+cy

(a,b)(b,c)=(ax+by)(bx+cy)=(abx^2 + acxy+ b^2 xy + bcy^2)
I am not sure how to factor a ax+cy out of that...

3. Let $\displaystyle p_1,...,p_n$ be the set of primes which divide either one of $\displaystyle a,b \mbox{ or } c$. Write

$\displaystyle a=p_1^{\alpha_1}\hdots p_n^{\alpha_n}$

$\displaystyle b=p_1^{\beta_1}\hdots p_n^{\beta_n}$

$\displaystyle c=p_1^{\gamma_1}\hdots p_n^{\gamma_n}$

be the canonical factorizations of $\displaystyle a,b,c$, where some of the exponents may be 0. Then, letting $\displaystyle M(x,y)=\mbox{max }\{x,y\}$,

$\displaystyle \mbox{lcm }(a,b)=p_1^{M(\alpha_1,\beta_1)}\hdots p_n^{M(\alpha_n,\beta_n)}$

$\displaystyle \mbox{lcm }(b,c)=p_1^{M(\gamma_1,\beta_1)}\hdots p_n^{M(\gamma_n,\beta_n)}$

and hence

$\displaystyle \frac{\mbox{lcm }(a,b)\mbox{lcm }(b,c)}{b}=p_1^{M(\alpha_1,\beta_1)+M(\gamma_1,\be ta_1)-\beta_1}\hdots p_n^{M(\alpha_n,\beta_n)+M(\gamma_n,\beta_n)-\beta_n}$

Now you just need to show that, for every $\displaystyle 1 \leq j \leq n$, we have $\displaystyle M(\alpha_j,\beta_j)+M(\gamma_j,\beta_j)-\beta_j\geq M(\alpha_j,\gamma_j)$. Hint : consider separately the case where $\displaystyle M(\alpha_j,\gamma_j)=\alpha_j$ and the case where $\displaystyle M(\alpha_j,\gamma_j)=\gamma_j$.

4. Thanks.

Shouldn't the two cases be $\displaystyle M(\alpha_j,\gamma_j)=\alpha_j$ and $\displaystyle M(\alpha_j,\gamma_j)=\gamma_j$?

If so, would this be ok?
If $\displaystyle M(\alpha_j,\gamma_j)=\alpha_j$, then $\displaystyle \alpha_j \geq \gamma_j$
If $\displaystyle \beta_j \geq \alpha_j$, then we have $\displaystyle \beta_j + \beta_j - \beta_j \geq \alpha_j$, which is true.
If $\displaystyle \beta_j \leq \alpha_j$, then we have $\displaystyle \alpha_j + M(\gamma_j,\beta_j) - \beta_j \geq \alpha_j$, which is true because then $\displaystyle M(\gamma_j,\beta_j) \geq \beta_j$

If $\displaystyle M(\alpha_j,\gamma_j)=\gamma_j$, then $\displaystyle \alpha_j \leq \gamma_j$
If $\displaystyle \beta_j \geq \gamma_j$, then we have $\displaystyle \beta_j + \beta_j - \beta_j \geq \gamma_j$, which is true.
If $\displaystyle \beta_j \leq \gamma_j$, then we have $\displaystyle \gamma_j + M(\alpha_j,\beta_j) - \beta_j \geq \gamma_j$, which is true because then $\displaystyle M(\alpha_j,\beta_j) \geq \beta_j$

5. Flawless! Good job.

There may be a shorter way... but when you have proofs with greatest common divisors and least common multiples, a guaranteed path to success is to translate the identity you wish to prove as a statement about the canonical factorization of the numbers involved. It might be hard work but it always takes you where you want to go - just be careful choosing a good notation so you don't hit a brick wall.

I corrected my post above - thanks for the heads up

6. I know this is done, but I just wanted to point something out that could help in the future ...

This was written down:
(a,c)=ax+cy
(a,b)=ax+by
(b,c)=bx+cy

But we can not assume that all the x and y are the same ... that's the bit that could help in the future ... make sure you distinguish your variables:

Another way to prove this is:

definition of lcm[a,b]=d is the d is the smallest integer such that a|d and b|d
let [a,b] = d, [a,c] = e, and [b,c] = f
since b|d and b|f, let bx=d and by=f

We are trying to show that [a,c]|[a,b][b,c]/b ... in other words, e|df/b

df/b = bxf/b = xf and since c|f, c|df/b
df/b = dby/b = dy and since a|d, a|df/b

So a|df/b and c|df/b ... so df/b is a common multiple of a and c ... can you show that the [a,c] divides this common multiple?