I have some marbles which I’m trying to arrange in a rectangle, but so far I’ve had no luck.
If I arrange them in rows of $4$, there are $3$ marbles left over.
If I arrange them in rows of $5$, there is $1$ marble left over.
If I arrange them in rows of $7$, there are $6$ marbles left over.
I estimate that there are a bit more than $200$ marbles. How can I arrange all of them in a rectangle? (I won’t accept the trivial arrangement of rows of $1$ marble.)
If you prefer a more abstract statement of the problem, here it is: find the smallest $n\gt 200$ such that \begin{align*} n &\equiv 3 \pmod{4}\\ n &\equiv 1 \pmod{5}\\ n &\equiv 6 \pmod{7}. \end{align*} What are the divisors of $n$?
Similar problems were mentioned in The Mathematical Classic of Sunzi from fifth century China. There is a theorem about questions like this, known as the Chinese remainder theorem. Show hint
I’m going to cover the algebraic solution first, then talk about other methods you might have used. Since we have three equations, it might be better to express them in the normal manner (without mod notation) so we can apply the techniques we’ve already developed for solving simultaneous equations. \begin{align*} n &= 4a + 3\\ n &= 5b + 1\\ n &= 7c + 6 \end{align*} for integers $a$, $b$, and $c$. Taking the first and second equation together: \begin{align*} 4a + 3 &= 5b + 1\\ 4a &= 5b - 2\\ 4a &\equiv -2 \pmod{5}\\ &\equiv 3 \pmod{5} \end{align*} Now we have an equation similar to the one we solved in Question 7.9.4 with trial-and-error. In this case $a=2$ solves the equation, so we have \[a \equiv 2 \pmod{5}.\] Since we still haven’t used the equation $n = 7c + 6$, it might be better to rewrite this equation for $a$ without mod notation so we can solve simultaneous equations again. \begin{align*} a &= 2 + 5d\quad(\text{for some integer }d)\\ n &= 4a + 3\\ &= 4(2 + 5d) + 3\\ &= 20d + 11. \end{align*} Combining this with $n = 7c + 6$ we get \begin{align*} 7c + 6 &= 20d + 11\\ 7c &= 20d + 5. \end{align*} Now you can either think of this as \[7c\equiv 5\pmod{20}\] or \[20d\equiv -5 \pmod{7}\] or just try a few values for $c$ and $d$. You’ll find that $c\equiv15\pmod{20}$ or $d\equiv5\pmod{7}$. Let’s go with the latter and express it like this: \begin{align*} d &= 5 + 7e\quad(\text{for some integer }e)\\ n &= 20d + 11\\ &= 20(5 + 7e) + 11\\ &= 140e + 111. \end{align*} So at last we find that \[n \equiv 111 \pmod{140}.\] If $n$ is slightly more than $200$, it must be $140+111 = 251$, which unfortunately is prime (see Question 4.1.10 for an example of working out if a number is prime), so I can’t arrange the marbles in a rectangle.
Now onto non-algebraic methods of answering the question. You might reason that since the number of marbles leaves a remainder of $1$ when divided by $5$, its last digit must be a $1$ or a $6$. And if it leaves a remainder of $3$ when divided by $4$, it must be odd, so that rules out ending in $6$. It has to end in $1$.
There aren’t many values to try now. We could check $201,211,221,231,\ldots$ to see if they leave a remainder of $6$ when divided by $7$. Alternatively, we could write out the numbers that have that remainder ($202,209,216,223,\ldots$), and see if they end in $1$. In any case, the smallest suitable number is $251$. We’d need to check that it does in fact leave a remainder of $3$ when divided by $4$ (because all we took from that fact so far was that the number had to be odd).