How to apply constraints on a number

Question

I encountered the following question, which is a sample of similar questions.

A restaurant has a fixed number of chairs. If they are set around tables with a capacity of 7 (divide them into groups of 7), no chair is left over. If they are set around tables with a capacity of 4, there are two chairs left over. If they are set around tables with a capacity of 3, one chair is left over. How many numbers smaller than 1000 are there for the capacity of the restaurant?

I know that the problem states the following relationships:

$n= 7k_1 = 4k_2+2=3k_3+1$

With try and error (examining the numbers divisible by 7) I could find $70$, but it is time-consuming. However, I have no strategy to put this problem in a mathematic formula, and how to find the remaining numbers.

Answer 1

Firstly observe that the problem is equivalent to the following modular system

• $x\equiv 0 \pmod 7$
• $x\equiv 2 \pmod 4$
• $x\equiv 1 \pmod 3$

and the existence and uniqueness of the solution $\pmod{7\cdot4\cdot3}\,$ is guaranteed by CRT.

To solve we can observe that

• $x\equiv 0 \pmod 7 \implies x=7k$
• $x\equiv 2 \pmod 4\implies 3k\equiv 2 \pmod 4\implies -k=2+4h\implies x=14+28h$
• $x\equiv 1 \pmod 3\implies 2+h\equiv 1 \pmod 3 \implies h\equiv 2 \pmod 3\implies h=2+3s \\\implies x=70+84s$

Therefore all the solutions are

$$x=70, \,70+84,\, 70+2\cdot 84,...$$

More informally in this simple case we can also find $70$ by inspection as you did and then note that we can add up multiple factors $7\cdot4\cdot3=84$ to obtain others solution (in any case for the uniqueness we should always refer to CRT).

Answer 2

If you don't know the Chinese Remainder Theorem:

Notice;

$n = 7k_1 = 4k_2 + 2 = 3k_3 + 1$

We want to get rid of those $+2$ and $+1$ by adding or subtracting multiples of $7$. $1-7 = -6 = -2*3$ for example or $1 + 14 = 15= 5*3$

$n = 7k_1 = 4k_2 + 2 = 3k_3 - 6+7$

$n - 7 = 7(k_1-1) = 4k_2 - 5 = 3(k_3 -2)$

$n-7 = 7(k_1-1) = 4(k_2 -1) - 1 = 3(k_3 -2)$

Now we want to get rid of that $-1$ by adding or subtracting a multiple of $3*7 = 21$. Example $-1 + 21 = 20 = 4*5$ or ... gee... $-1 - 63 = -64 = -17*4$.

$n-7 = 7(k_1-1) = 4(k_2 -1)+20 - 21 = 3(k_3 -2)$

$n+14 = 7(k_1 -1)+21 = 4(k_2 -1) + 20 = 3(k_3 -2) + 21$

$n+14 = 7(k_1 +2) = 4(k_2 +4) = 3(k_3 + 5)$

This will work if $(k_1+2) = 3*4=12$ and $(k_2 + 4) = 7*3=21$ and $k_3 + 5 = 4*7=28$ and $n+14 = 7*3*4 = 84$

In other words if $k_1 =10; k_2 = 17; k_3 = 23$ and $n = 70 = 7*10 = 4*17+2 = 3*23 + 1$.

But ... it's easier to learn the Chinese Remainder Theorem.

=====

Alternatively we can do it through successive remainders.

$n = 3*4*7q + r=84q + r; 0\le r < 84$.

$r = 28p + s$ where $0\le s < 28$ and $0 \le p < 3$ but

$n = 7(12q + 4p) + s= 7k_1$ we know $7$ divides $s$ so $s= 0,7,14$.

But we also have

$n = 4(21q + 7p) + s = 4k_2 + 2$ so $s$ is two more than a multiple of $4$. The only choices of $0,7,14$ that satisfy that is $s = 14$. So $s = 14$

So $r = 28p + 14$ where $0\le p < 3$ so $r =14,42, $ or $70$.

But $n = 84q + r = 3*28q + r =3k_2 + 1$ so $r$ is one more than a multiple of $3$. $r = 70$ is the only option that works.

So $n =84q + 70$. It doesn't actually matter what $q$ is. As $3,4,7$ all divide $84$ all $84q+70$ will have the same remainders when divided by $3,4,7$ so all of them are solutions.

But, really, just learn the Chinese Remainder Theorem. You wont regret it.