Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number Theory Problem

Tags:
  1. Apr 9, 2010 #1
    1. The problem statement, all variables and given/known data

    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?

    2. Relevant 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.

    3. 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.
     
  2. jcsd
  3. Apr 9, 2010 #2
    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 [itex]x\equiv a \pmod b[/itex] 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).
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook