# What is a simple solution to this system of 5 linear congruences?

\begin{cases}E\equiv -1 \pmod{5}\\ E\equiv 3 \pmod{6} \\E\equiv 0 \pmod{7} \\E\equiv 1 \pmod{8} \\E\equiv 0 \pmod{9}\end{cases}

I was given an egg basket puzzle asking for the number of eggs in the basket, the puzzle translates to the above system of linear congruences.

I solved it by brute force using Linear Diophantine Equations, but I think there is a quicker, more clever way to solve this problem since it's supposed to be a puzzle and not strictly a math question.

• Well, $E$ is divisible by $63$ for starters. – Simply Beautiful Art Feb 18 '17 at 16:23

You might notice that $E=9$ is a solution to all the congruences except the middle one. The $\mbox{lcm(5,6,8,9)} = 360,$ so now you have the system

$$E\equiv 9 (\bmod{360})$$ $$E\equiv 0 (\bmod{7})$$

You need $360k +9$ to be a multiple of $7$, so reduce mod $7$ to get

$$360k+9 \equiv 3k +2 (\bmod{7})$$

which has solution $k=4$. Final answer $360\cdot 4 +9 = 1449$.

• See my answer for the general idea behind the optimization implicitly employed above to "notice" the solution $E = 9.\$ – Bill Dubuque May 3 '17 at 15:59

Like @Simply Beautiful Art stated, the number is divisible by 63. So we have that the number is $63k$ for some k. Now, $63k\equiv -k\equiv1\pmod{8}\implies k=8u-1$ for some u. So now our number is $63(8u-1).$ Taking is mod 6, we have $63(8u-1)\equiv 3(2u-1)\equiv3\pmod{6}$ so no new information here. Taking it mod 5 we have $63(8u-1)\equiv 3(3u-1)\equiv 9u-3\equiv 4u+2\equiv -1\pmod{5}\implies 2u\equiv 1\pmod{5}\implies u\equiv 3\pmod{5}.$ So our final answer is any number that is in the form $63(8(5x+3)-1)$ for some integer x, and taking $x=0$ gives 1449.

${\bf Hint}\ \ \ \ {\rm If}\ \ \ \begin{array}{rl} n=\!\!\!\!&\color{#c00}{a+b} &x\!\!\!\! &\equiv \color{#c00}a\pmod{\color{#c00} b}\\ =\!\!\!\! &\color{#0a0}{c+d}\ \ \ \ {\rm then}\ &x\!\!\!\!&\equiv \color{#0a0}c\pmod{\color{#0a0} d}\\ =\!\!\! &{e+f} &x\!\!\!\! &\equiv e\pmod f\end{array}\!\iff\, x\equiv n\pmod{{\rm lcm}(b,d,f)}$

{\bf Proof}\ \ \ \begin{align} x&\equiv a\equiv a+b\equiv n\!\!\!\pmod b\\ x&\equiv c\equiv c+d\equiv n\!\!\!\pmod d\\ x&\equiv e\equiv e+f\equiv n\!\!\!\pmod f\end{align}\!\! $\iff b,d,f\mid x-n\iff {\rm lcm}(b,d,f)\mid x-n$