1
$\begingroup$

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]$?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ (NOT RELATED ) $\frac {4100}{25}=164$ ??? $\endgroup$ – освящение Mar 28 '18 at 5:46
  • $\begingroup$ Yes, You can check this by multiplication. I don't see why you need me to verify it, though. $\endgroup$ – астон вілла олоф мэллбэрг Mar 28 '18 at 22:44
  • $\begingroup$ oh man ! I was just kidding . As I was the 4100th profile viewer."OFFER VALID TILL (my) MARRIAGE : If your visitor number is a multiple of 25 then you may request me to answer any one (community-acceptable)question of yours, or inspect any one answer of yours. I am not the most proficient on this website, but I can put up good services in undergraduate topics." ;) (After fun we'll have to delete our comments , though .) $\endgroup$ – освящение Mar 29 '18 at 4:54
  • $\begingroup$ Oh. That's fine, very fine indeed. Thank you for availing the offer. $\endgroup$ – астон вілла олоф мэллбэрг Mar 29 '18 at 4:59
1
$\begingroup$

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

$\endgroup$

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.