Elementary Number Theory – Proving LCM Inequality

elementary-number-theorygcd-and-lcm

Apart from changing $p$ to $q$, this is from an unanswered question that the OP deleted about a week ago. It asks to prove

$$\operatorname{lcm}(m, q)=\operatorname{lcm}(n, q) \;\;\to\;\; \operatorname{lcm}(m + n, q) \ge \operatorname{lcm}(n, q) \tag{1}\label{eq1A}$$

Although the original question doesn't specify what the variables are, this question will have them all be positive integers. Using the $p$-adic valuation function, a sufficient condition to prove the RHS of \eqref{eq1A} is that, for all primes $p$,

$$\nu_p(\operatorname{lcm}(m + n, q)) \ge \nu_p(\operatorname{lcm}(n, q)) \tag{2}\label{eq2A}$$

Using the prime factorizations, we get for the LHS of \eqref{eq1A} for some non-integer $r$ that

$$\nu_p(\operatorname{lcm}(m, q)) = \max(\nu_p(m), \nu_p(q)) = \nu_p(\operatorname{lcm}(n, q)) = \max(\nu_p(n), \nu_p(q)) = r \tag{3}\label{eq3A}$$

If $\nu_p(q) = r$, then $\nu_p(\operatorname{lcm}(m + n, q)) \ge r$. Otherwise, we have $\nu_p(m) = \nu_p(n) = r$, so $p^r \mid m \;\land\; p^r \mid n \;\to\; p^r \mid m + n$. Thus, we once again have $\nu_p(\operatorname{lcm}(m + n, q)) \ge r$. This means \eqref{eq2A} holds in both cases, proving the RHS of \eqref{eq1A} is true.

Are there other methods to prove this?

Best Answer

Using notation $\begin{align}[x,y] &:= {\rm lcm}(x,y),\\ (x,y)&:= \gcd(x,y)\end{align}\,$ and $\,\color{#c00}{\rm D}:=$ lcm distributes over gcd

$\qquad\underbrace{[q,n]=(\color{#0af}{[q,m]},[q,n])}_{\textstyle \color{#0af}{[q,m]}=[q,n]} \overset{\color{#c00}{\rm D}}= [q,\color{#0a0}{(m,n)}]\ {\large \mid}\ [q,\color{#0a0}{m\!+\!n}]\ $ since $\ \color{#0a0}{(m,n)\mid m\!+\!n}$

Related Question