Solve Ancient Indian Number Theory Problem | Minimum Number of Eggs in a Basket

[coreyB]

Homework Statement

i'm sure everyone has seen this:

Solve the following ancient Indian problem: If eggs are removed from a basket 2, 3, 4,
5, and 6 at a time, there remain, respectively, 1, 2, 3, 4, and 5 eggs. But if the eggs are
removed 7 at a time, no eggs remain. What is the least number of eggs that could have
been in the basket?

Homework Equations

x=1%2
x=2%3
x=3%4 implies %2 (dropped)
x=4%5
x=5%6 impies %2,3 (dropped)
x=0%7

this leaves just four equations.

The Attempt at a Solution

x=1%2
x=2k+1

x=2%3
2k+1=2%3
2k=1%3
k=2%3
k=3p+2
and x=2k+1 so x= 2(3p+2)+1 = 6p+5

x=4%5
6p+5=4%5
6p=4%5
p=4%5
p=5j+4
and x=6p+5 so x=6(5j+4)=5 = 30j+29
30j+29

x=0%7
30j+29=0%7
30j=6%7
j=3%7
j=7r+3
and x=30j+29 so x=30(7r+3)+29=210r+119

so x=119%210 = 119.

how does this look? feedback appreciated.

 

[rasmhop]

I think you may have dropped too many of your equations. Am I right in assuming that you have solved the problem on the assumption that the equation %4 and %6 can be dropped as they are implied by the others? That seems to be the case given how you solved it, but this is not valid. Consider x=329. This satisfies all equations except x=3%4 so you cannot drop that. You can drop %2 and %6 but keeping %3 and %4.

Anyway what kind of a theoretical foundation do you have? Your use of x=a%b instead of x\equiv a \pmod b suggests you may be new to number theory, or just feel that is the easiest notation to type in. If the former is the case, then your approach seems fine though it really needs some explanation (I haven't bothered to check it in details, but the approach seems to be valid). If you do know a bit of elementary number theory then you should be able to use the Chinese remainder theorem to solve this very quickly and efficiently (this is exactly what it is for).