# Chinese remainder theorem problem

• Benny
In summary, the question involves fifteen pirates trying to divide a stack of identical gold coins. After two pirates are killed in arguments, the remaining pirates try to distribute the coins evenly and are successful. To find the smallest number of coins, the Chinese Remainder Theorem is used to set up equations. The equations x = 2(mod15), x = 1(mod14), and x = 0(mod13) are used, with the number of pirates being important in the equations. The context of the question is amusing and the congruence relation is used to simplify expressions. However, it is important to understand the meaning of the remainder in the congruence relation. In this case, the remainder is the difference between a and b
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?

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

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

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

Benny said:
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)

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.

## 1. What is the Chinese Remainder Theorem problem?

The Chinese Remainder Theorem is a mathematical concept that deals with finding a solution to a system of congruences. It states that if we have a set of pairwise relatively prime moduli, we can find a unique solution to the system of congruences using the Chinese Remainder Theorem.

## 2. How does the Chinese Remainder Theorem work?

The theorem uses modular arithmetic to find a unique solution to a system of congruences. It involves finding the least common multiple of the moduli, and then using this number to find the solution through a series of calculations.

## 3. What is the significance of the Chinese Remainder Theorem?

The Chinese Remainder Theorem has many practical applications, especially in computer science and cryptography. It is used in algorithms for finding large prime numbers and in error-correcting codes. It also has applications in solving systems of linear equations and in solving polynomial equations.

## 4. What are the limitations of the Chinese Remainder Theorem?

The Chinese Remainder Theorem can only be applied to a system of congruences if the moduli are pairwise relatively prime. If this condition is not met, the theorem cannot be used and a different method must be used to solve the system of congruences.

## 5. Can the Chinese Remainder Theorem be used in all situations?

No, the Chinese Remainder Theorem can only be used in situations where the moduli are pairwise relatively prime. If the moduli are not relatively prime, the theorem cannot be applied and another method must be used to solve the system of congruences.

• Linear and Abstract Algebra
Replies
5
Views
1K
• Precalculus Mathematics Homework Help
Replies
5
Views
2K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Precalculus Mathematics Homework Help
Replies
4
Views
1K
• Precalculus Mathematics Homework Help
Replies
3
Views
3K
• General Math
Replies
4
Views
2K
• Calculus and Beyond Homework Help
Replies
1
Views
2K
• Calculus and Beyond Homework Help
Replies
9
Views
2K
• Calculus and Beyond Homework Help
Replies
1
Views
3K
• Linear and Abstract Algebra
Replies
12
Views
4K