1
$\begingroup$

\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}

Answer: 1449

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.

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

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

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

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.

$\endgroup$
0
$\begingroup$

${\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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.