Wednesday, 16 July 2014

proof writing - Modular Arithmetic - Pirate Problem

I was reading an example from my book, and I need further clarification because I don't understand some things. I'm just going to include the f1 part in full detail because f2 and f3 are identical.



Consider the following problem.



Once upon a time, a band of seven pirates seized a treasure chest containing some gold coins (all of equal value). They agreed to divide the coins equally among the group, but there were two coins left over. One of the pirates took it upon himself to throw the extra coins overboard to solve the dilemma. Another pirate immediately dived overboard after the sinking coins and was never heard from again. After a few minutes, the six remaining pirates redivided the coins and found that there were three coins left. This time a fight ensured and one pirate was killed. Finally, the five surviving pirates were able to split the treasure evenly. What was the least possible number of coins in the treasure chest to begin with?




If x represents the original number of coins, then the first division can be represented by the congruence



x2 (mod 7) [I understand this part because originally we had 7 pirates and 2 left over coins]



The second and third division give the congruences
x23 (mod 6) and x20 (mod 5).
[The second division is the 2 coins that were thrown overboard, the pirate jumping into the ocean is the new mod, and there are 3 coins leftover. The third division is the original 2 coins thrown overboard, the 5 surviving pirates, and nothing is left over].



So the system of congruences is x2 (mod 7), x5 (mod 6), and x2 (mod 5)




We solve the system by letting x=2f1+5f2+2f3



where f1,f2, and f3 (to be determined soon ) satisfy



f11 (mod 7)
f20 (mod 7)
f30 (mod 7)



f10 (mod 6)
f21 (mod 6)

f30 (mod 6)



f10 (mod 5)
f20 (mod 5)
f31 (mod 5)



[Where are they getting this from?]



To compute f1 we set f1=6×5×b1 where b1 satisfies the single congruence 6×5×b11 (mod 7)
[Ok. That 6 and 5 comes from mod 6 and mod 5, but why is there a 1 at the end of the equation?]




Note that f1 is necessarily divisible by 6 and by 5 and is congruent to 1 modulo 7. Thus f11 (mod 7), f10 (mod 6), and f10 (mod 5)



To solve the congruence, reduce 6×5 modulo 7 to get 2b11 (mod 7) [ 6×5=30, so if I divide 30 by 7, I would get a remainder of 2 because 7×4=28 and 3028=2.



Note that b1=4 is a solution. [WAIT! Where did that 4 come from? Now I'm really confused. What are the steps?]

No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...