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 $f_1$ part in full detail because $f_2$ and $f_3$ 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



$x \equiv 2 $ (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
$x - 2 \equiv 3$ (mod $6$) and $x-2 \equiv 0 $ (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 $x \equiv 2$ (mod 7), $x \equiv 5$ (mod 6), and $x \equiv 2$ (mod 5)




We solve the system by letting $x= 2f_1+5f_2+2f_3$



where $f_1,f_2$, and $f_3$ (to be determined soon ) satisfy



$f_1 \equiv 1$ (mod 7)
$f_2 \equiv 0$ (mod 7)
$f_3 \equiv 0$ (mod 7)



$f_1 \equiv 0$ (mod 6)
$f_2 \equiv 1$ (mod 6)

$f_3 \equiv 0$ (mod 6)



$f_1 \equiv 0$ (mod 5)
$f_2 \equiv 0$ (mod 5)
$f_3 \equiv 1$ (mod 5)



[Where are they getting this from?]



To compute $f_1$ we set $f_1 = 6 \times 5 \times b_1$ where $b_1$ satisfies the single congruence $ 6 \times 5 \times b_1 \equiv 1$ (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 $f_1$ is necessarily divisible by 6 and by 5 and is congruent to 1 modulo 7. Thus $f_1 \equiv 1$ (mod 7), $f_1 \equiv 0$ (mod 6), and $f_1 \equiv 0$ (mod 5)



To solve the congruence, reduce $ 6 \times 5$ modulo 7 to get $2b_1 \equiv 1$ (mod 7) [ $ 6 \times 5 = 30 $, so if I divide 30 by 7, I would get a remainder of 2 because $ 7 \times 4 = 28$ and $ 30-28=2$.



Note that $b_1 = 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 $lim_{hrightarrow 0}frac{sin(ha)}{h}$

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