1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Chinese remainder theorem problem

  1. Aug 12, 2005 #1
    I'm having a lot of trouble setting up the equations for the following question where I need to use the chinese remainder theorem.

    Q. Fifteen pirates steal a stack of identical gold coins. When they try to divide them evenly, two coins are left over. A fight erupts and one of the pirates is killed. The remaining pirates try again to evenly distribute the coins. This time there is one coin left over. A second pirate is killed in the resulting argument. Now when the remaining pirates try to divide the coins evenly there are no coins left over. Use the Chinese Remainder Theorem to find the smallest number of coins that could have been in the sack.

    The first thing that I'm unsure about is what the number of pirates left has to do with the question. If I ignore it I get the following equations.

    x = 2(mod2)
    x = 1(mod2)
    x = 0(mod2)

    But then I get x = 2(b_1)(4) + (1)(b_2)(4) + 0 (mod8)

    where b_1 is the multiplicative inverse of 4 in Z_2 and the other 4 is also the multiplicative inverse of 2 in Z_4. But gcd(4,2) not equal to one so b_1 and b_2 'can't exist.' So I must be doing something wrong. I'm not sure how to set up the equations so could someone please help me out?
     
  2. jcsd
  3. Aug 12, 2005 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Why "mod 2"? They aren't dividing the coins into two groups ("2 (mod 2)" is the same as 0- that should have been a warning!) they are dividing them among themselves. That's why the number of pirates is important.

    First, they divide the coins among 15 pirates and have two left over: x= 2 (mod 15).
    One pirate is then killed and the coins are dividing among the remaining 14 pirates and now there is one coin left over: x= 1 (mod 14).
    A second pirate is killed and now the coins can be divided evenly among the remaining 13 pirates: x= 0 (mod 13).

    The equations are x= 2 (mod 15), x= 1 (mod 14), x= 0 (mod 13).

    (Pirates have very effective methods of solving problems, don't they!)
     
  4. Aug 12, 2005 #3

    lurflurf

    User Avatar
    Homework Helper

    nice
    15-2=14-1=13-0
    much better than if the first time 11 were left and the second 7
     
  5. Aug 12, 2005 #4
    Thanks again for your help HallfsofIvy. I really need to be able to pick out the important information in questions. :grumpy:

    What I think has been a major weakness of mine throughout the entire topic is not understanding what a congruence relation [tex]a \equiv b\left( {\bmod m} \right)[/tex] actually means. I know how to use it to simplify expressions and other routine procedures like that but I'm not really sure where the 'remainder' is, in that congruence relation. All I can see is that it means m divides the difference between a and b.

    As a side note I thought the context chosen for the question was quite amusing :biggrin:
     
  6. Aug 12, 2005 #5

    lurflurf

    User Avatar
    Homework Helper

    in
    x=a (mod b)
    if a<b
    a is the remainder of x/b
    sometimes it is written
    a=mod(x,b)
    to make this more clear
    a side note crt is not needed for this problem
    (though it can be used for practice or to avoid thinking)
    we have
    x=0 (mod 13)
    x=1 (mod 14)
    x=2 (mod 15)
    by adding 13 to each side we have
    x+13=0 (mod 13,14,15)
    x+13=0 (mod 2730)(lcm(13,14,15)=13*14*15=2730)
    x=2730-13 (mod 2730)
    x=2717 (mod 2730)
     
  7. Aug 12, 2005 #6
    Interesting, I didn't think it could be done any other way. But then again I'm not too experienced with this topic. Anyway thanks for the help.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Chinese remainder theorem problem
Loading...