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

Question

How do you answer

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.

The answer is 301.

Answer 1

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

Answer 2

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

Answer 3

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