If $k$ and $\ell$ are positive 4-digit integers such that $\gcd(k,\ell)=3$, what is the smallest possible value for $\mathop{\text{lcm}}[k,\ell]$?

Question

I am a student in middle school, so any easy-to-understand explanations would be very appreciated. Any hints or answers would be super helpful! I am stumped on this problem. I know that the product of two numbers is equal to the product of LCM and GCD of the two numbers. Am I meantto use this information to solve this problem?

If $k$ and $\ell$ are positive 4-digit integers such that $\gcd(k,\ell)=3$, what is the smallest possible value for $\mathop{\text{lcm}}[k,\ell]$?

Answer 1

Okay, so you know that the product of two numbers is the product of their lcm and their gcd, which is all well and good. So, $$kl = \operatorname{lcm}(k,l) \times \gcd(k,l) = 3 \operatorname{lcm}(k,l)$$

Now, if you have to minimize $\operatorname{lcm}(k,l)$, you essentially have to minimize the product $kl$, while ensuring that $\gcd(k,l) = 3$.

So we will make our problem even simpler. The product $kl$ is small if both $k$ and $l$ are small. But, both are greater than $999$ since both are four digit numbers. Further, they have $\gcd = 3$,so both are multiples of $3$.

It follows that $k,l \geq 1002$, which is the smallest four digit multiple of $3$. But, $k,l$ must have $\gcd = 3$, so they can't have anything other than $3$ as a common factor.

Let us now write down everything we know about $k,l$.

• $k,l \geq 1002$.

• $k,l$ are different multiples of $3$, and their $\gcd$ is $3$.

Now, it is an insight which helps us. First, we would like to fix $k = 1002$, and see which $l$ satisfies the above conditions. For this, we use a nice result.

---

If $k$ and $l$ are multiples of $3$ such that $l=k+3$, then $\gcd(k,l) = 3$.

Proof : Certainly, $3$ is a common divisor of $k$ and $l$. Also, if $d$ divides $k$ and $d $ divides $l$, then $d$ divides $l-k = 3$, so $d = 1$ or $d = 3$. Therefore, $3$ is the greatest common divisor of $k$ and $l$.

---

Using the above, with $k = 1002$ gives us $l = 1005$. Also, $l = 1005$ is the smallest four digit number which has $\gcd(k,l) = 3$. Therefore, the answer in this case, is $\frac{1002 \times 1005}{3} = 335670 = \operatorname{lcm}(l,k)$.

Note : If you take $l=1002$, then $k = 1005$ will work, giving the same result $335670$.

---

Now, if neither $k,l$ is $1002$, then both have to be greater than $1005$. In particular, their $\operatorname{lcm}$ is greater than or equal to $\frac{1005 \times 1005}{3} = 336675 > 335670$. So, the value of the $\operatorname{lcm}$ is greater than $335670$.

Both logics above combine to tell us that the smallest value of $\operatorname{lcm}(k,l)$ is $335670$.

Answer 2

So $kl = \gcd(k,l) \operatorname{lcm}(k,l)$ so

$ \operatorname{lcm}= \frac {kl}3$.

So the smallest such value will come from the smallest two values of $k,l$.

$k$ and $l$ are mulitiples of $3$ so the smallest two values are $1002$ and $1005$ so the smallest possible LCM is $\frac {1002 \times1005}3=335670$.