Brahmagupta's egg basket

Number Theory Level 2

Brahmagupta has a basket full of eggs. When he takes the eggs out of the basket 2 at a time, there is 1 egg left over. When he takes them out 3 at a time, there are 2 eggs left over. Likewise, when he takes the eggs out 4, 5, and 6 at a time, he finds remainders of 3, 4, and 5, respectively. However, when he takes the eggs out 7 at a time, there are no eggs left over.

What is the least amount of eggs that could be in Brahmagupta's basket?

The answer is 119.

2 solutions

Andrew Hayes Staff
Jan 17, 2017

Relevant wiki: Chinese Remainder Theorem

This problem can be written as a system of linear congruences:

$\begin{cases}\begin{aligned} x &\equiv 1 \pmod{2} \\ x &\equiv 2 \pmod{3} \\ x &\equiv 3 \pmod{4} \\ x &\equiv 4 \pmod{5} \\ x &\equiv 5 \pmod{6} \\ x &\equiv 0 \pmod{7}. \end{aligned}\end{cases}$

This can be reduced to the equivalent system of congruences:

$\begin{cases}\begin{aligned} x &\equiv 2 \pmod{3} \\ x &\equiv 3 \pmod{4} \\ x &\equiv 4 \pmod{5} \\ x &\equiv 0 \pmod{7}. \end{aligned}\end{cases}$

Updated per the reply of @Brian Charlesworth.

Note that the first three congruences can be rewritten:

$\begin{cases}\begin{aligned} x &\equiv -1 \pmod{3} \\ x &\equiv -1 \pmod{4} \\ x &\equiv -1 \pmod{5}. \end{aligned}\end{cases}$

Since these constants are the same, a "shortcut" can be taken with the Chinese Remainder Theorem. The LCM of these moduli is 60, so

$\begin{aligned} x &\equiv -1 \pmod{60} \\ &\equiv 59 \pmod{60} \end{aligned}$

Write this congruence as an equation, and substitute the expression for $x$ into the final congruence:

$\begin{aligned} x &= 60j+59 \\ 60j+59 &\equiv 0 \pmod{7} \\ j &\equiv 1 \pmod{7} \end{aligned}$

Then write this congruence as an equation, and substitute it into the expression for $x:$

$\begin{aligned} j &= 7k+1 \\ x &= 60(7k+1)+59 \\ x &= 420k + 119 \\ x &\equiv 119 \pmod{420} \end{aligned}$

Thus, the least amount of eggs that could be in Brahmagupta's basket is $\boxed{119}.$

I suppose that we could also note that $(x + 1) | lcm(2,3,4,5,6) = 60$ , and so we are looking for the least $x = 59 + 60n$ such that $7|x$ . Then

$7|(59 + 60n) \Longrightarrow 7|(3 + 4n) \Longrightarrow n = 1, x = 59 + 60 = \boxed{119}$ .

Brian Charlesworth - 4 years, 4 months ago

That's pretty good! I will update my solution to reflect this.

Andrew Hayes Staff - 4 years, 4 months ago

How did you reduce the congruences to 4 congruences?

Randall Kim - 2 years, 11 months ago

If you have $x \equiv 3 \pmod{4},$ then $x \equiv 1 \pmod{2}$ is redundant.

Likewise, if you have $x \equiv 2 \pmod{3}$ and $x \equiv 3 \pmod{4},$ then $x \equiv 5 \pmod{6}$ is redundant.

Andrew Hayes Staff - 2 years, 11 months ago

Can you pls explain this? In 1st case, you have retained the larger number (mod 4) and eliminated its factor 2. Whereas in 2nd case, you have retained factors (mod 3), (mod 4) and eliminated (mod 6).

anant shirgaonkar - 1 year, 9 months ago

Syed Hissaan
Feb 1, 2017

the other way is using the brute force ;

since we know that the number is odd because $x=1(mod 2)$ .............. 1

we also know that $x=4(mod 5)$ there for the number must have a last digit of $5$ because it can't be zero since the number is odd .

using the fact that $x=4(mod 5)$

we can write it as : $5k+4$ ; where $k$ belongs to { 1,3,5,7.....})

now feeding in the values we can find that for $k=9 => 5(9) +4 =119$

checking 119 for all the values , we can see that it satisfies all the given conditions . so 119 is our answer .

Brahmagupta's egg basket

The answer is 119.

2 solutions

0 pending reports