# Explain Least Common Multiple problem to an 11 year old i.e. without number theory or brute force

Sue has some buttons. If she arranges them in rows of either 2, 3, 4, 5, or 6 she has one button left over. If she arranges them in rows of 7 she has no buttons left over. What is the least possible number of buttons that sue has?

without number theory or brute force please?

Okay we want to find the smallest positive integer N such that N=r⋅lcm(2,3,4,5,6)+1 is a multiple of 7 for some integer r. How do I do that, and how do I explain to an 11 year old? There's apparently supposed to be a trick to this because it's in a standardised exam.

Or I guess based on this:

It looks like we want to minimise z s.t.

$$z = 2x_2+1=3x_3+1=4x_4+1=5x_5+1=6x_6+1=7x_7$$

where $x_i$'s are integers, which I think is linear programming or something. Help please.

• Pictures generally work well for young kids. Commented Mar 4, 2017 at 14:55
• Well, I suppose I'd just do it by trial and error. As you point out, we are looking for the least multiple of $60$ which is $1$ less than a multiple of $7$. So, we try $60\times 1$. No good. $60\times 2$, not good. The answer is just $60\times 4$ so trial and error works very quickly here.
– lulu
Commented Mar 4, 2017 at 14:57
• I'm somewhat surprised the numbers are so large. For $11$ year olds, I'd have stuck with smaller numbers. But of course, you can illustrate the concept using smaller numbers.
– lulu
Commented Mar 4, 2017 at 14:58
• "Without number theory"? Isn't that like explaining what a dollar is without mentioning money? Commented Mar 4, 2017 at 15:01
• Correction, I wrote "the answer is just $60\times 4$". That was a typo. The correct answer is $60\times 5$.
– lulu
Commented Mar 4, 2017 at 15:08

Ask her, if you take away one button, what can you say about the number of buttons that are left? (Well, it's divisible by all of 2, 3, 4, 5, 6). So if it's divisible by all of those, what number must it be divisible by? And go from there. This kind of talks around both the concept of LCM and the formula $r(lcm)+1$.

• Sorry for the confusion. She already realised that it's something to do with LCM. Wait you have another solution than aras? Thanks rogerl! ^-^
– BCLC
Commented Mar 4, 2017 at 15:12

I think it's going to be hard to explain this to an eleven year old without any number theory or brute force. Here's an explanation that only uses the basics of both techniques. It might be a good option for somebody with not much mathematical maturity.

The big clue here is that the number of buttons is divisible by $7$. So it is some multiple of $7$: $7\cdot 1$, $7 \cdot 2$, $7 \cdot 3$, et cetera. Let's call our number $7 \cdot k$. However we also know that when our number is divided by $2,3,4,5$ and $6$, the remainder is $1$.

Since the remainder when dividing our number by $5$ is $1$, it has to end in a $1$ or a $6$. But since the number is not divisible by $2$, it has to end in $1$. We have $7 \cdot k = ???1$, so $k$ has to end in a $3$.

$k = 3$: Doesn't work ($7 \cdot 3 = 21$ divisible by 3)

$k = 13$: Doesn't work ($7 \cdot 13 = 91$ doesn't leave remainder 1 when divided by $4$)

$k = 23$: Doesn't work ($7 \cdot 23 = 161$ doesn't leave remainder 1 when divided by $3$)

$k = 33$: Doesn't work (divisible by 3)

$k = 43$: Works! ($7 \cdot 43 = 301$)

So the solution is $\boxed{301}$.

• $91-1=90$ is not divisible by $4$.
– lulu
Commented Mar 4, 2017 at 14:58
• @lulu WHoops, will edit.
– aras
Commented Mar 4, 2017 at 14:59
• The answer is 301. You can check on Excel.
– BCLC
Commented Mar 4, 2017 at 15:07
• @BCLC Yes, I realize. See edited answer.
– aras
Commented Mar 4, 2017 at 15:08
• Thanks aras! ^-^ So the key is knowing that 1. the number has to end in 1 or 6 because of remainder 1 when DB5, 2. it's 1 because of remainder 1 when DB2 and 3. the number is $7k$ where $k$ has to end in 3?
– BCLC
Commented Mar 4, 2017 at 15:11

Starting from the bottom pair of the "one button left over" set, how can we get one button left over from both rows of $2$ and $3$? We need an odd number that's also one more than a multiple of three - so we need one more than an even multiple of $3$.

Adding $4$ into the mix, we need one more than a multiple of four and one more than an even multiple of $3$. So after a little investigation we'll find that we need one more than a multiple of $3\times 4 = 12$.

Now add the requirement on multiples of $5$, and again a little shows that the only multiples of $12$ that are going to fulfill this are fifth multiples, that is multiples of $5\times 12 = 60$.

Happily we find that the requirement on multiples of $6$ is already fulfilled by looking for one more than a multiple of $60$.

Then we need to find a multiple of $60$ that is one less than a multiple of $7$. Without allowing modular tools, this is pretty much easiest just checking the multiples of $60$ to find $5\times 60+1 = 301 = 43\times 7$.