5
$\begingroup$

Given $n \geq 3$, what maximum LCM of any three numbers $\leq n$ can we obtain?

Now, if $n$ is odd, the answer would be $$n(n - 1)(n - 2)$$ because $\newcommand{\lcm}{\operatorname{lcm}}$ $$\begin{align*} \lcm(a, b, c) &= \lcm(a, \lcm(b, c))\\\\ &= \lcm\left(a, \frac{bc}{\gcd(b, c)}\right)\\\\ &=\frac{abc}{\gcd(b, c) \gcd(a, \frac{b c}{\gcd(b, c)})} \end{align*}$$

Now, if $b = a + 1$ and $c = a + 2$ where $a$ is odd, then $$\gcd(a, c) = \gcd(a, a + 2) = 1$$ Also, we know that $\gcd(a, a + 1) = 1$ for any $a$. We can simplify the formula as $$\begin{align*} \frac{abc}{\gcd(b, c) \gcd(a, \frac{b c}{\gcd(b, c)})} &= \frac{a (a + 1) (a + 2)}{1 \cdot \gcd(a, \frac{b c}{1)})}\\\\ &= \frac{a (a + 1) (a + 2)}{\gcd(a, bc))} \end{align*}$$

Also since, $a$ and $b$ are coprime and $a$ and $c$ are coprime, we must have $a$ and $bc$ coprime too, i.e., $\gcd(a, bc) = 1$. So, the maximum value of LCM for odd $n$ would be $$n (n - 1)(n - 2)$$

Now, how should I proceed for even $n$?

$\endgroup$
4
$\begingroup$

If $n$ is even and $\ge 4$, and not divisible by $3$, use $n(n-1)(n-3)$.

If $n$ is even and divisible by $3$, use $(n-1)(n-2)(n-3)$.

$\endgroup$
  • 1
    $\begingroup$ What is the logic? I mean proof that we can't obtain more than that. $\endgroup$ – nitrogen Jul 2 '15 at 17:45
  • $\begingroup$ In the examples I give, the numbers are pairwise relatively prime, so the lcm is their product. Now it is a matter of eliminating the only possible competition. For the first, the only $3$ numbers that give a greater product are $n,n-1,n-2$, but they have a smaller lcm. since the lcm of these three is $(n)(n-1)(n-2)/2$. For the divisible by $3$ case, the only ways to get a bigger product are to use $n,n-1,n-2$ or $n, n-1,n-3$ but these give lcm $n(n-1)(n-2)/2$ and $n(n-1)(n-3)/3$ respectively, each smaller than $(n-1)(n-2)(n-3)$. $\endgroup$ – André Nicolas Jul 2 '15 at 17:55
  • $\begingroup$ Nice one. Also could you help me out understanding my other problem, about graph. You can see my profile. $\endgroup$ – nitrogen Jul 2 '15 at 18:25

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.