Chinese remainder theorem problem

[Benny]

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?

 

[HallsofIvy]

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!)

 

[lurflurf]

nice
15-2=14-1=13-0
much better than if the first time 11 were left and the second 7

 

[Benny]

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 $$a \equiv b\left( {\bmod m} \right)$$ 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

 

[lurflurf]

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 $$a \equiv b\left( {\bmod m} \right)$$ 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

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)

 

[Benny]

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.