1
$\begingroup$

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?]

$\endgroup$
  • $\begingroup$ In $2 b_1 \cong 1 \mod 7$, try $b_1 = 1$, ${}=2$, ..., ${} = 7$ sequentially. Which one is a solution? That's where the "4" comes from. $\endgroup$ – Eric Towers Mar 9 '14 at 2:47
  • $\begingroup$ Am I just substituting the $b_1$ with 1, 2, 3, 4, 5, 6, 7? for mod 7 that would be $Z_7 [ 0,1,2,3,4,5,6]$ $\endgroup$ – usukidoll Mar 9 '14 at 2:49
  • $\begingroup$ As a random sample from the suggested seven step process: Substitute $3$ for $b_1$ in $2 b_1 \cong 1 \mod 7$. Do you get a valid congruence? (I.e., is the left side congruent to the right side?) No? Well, try again. There are only seven things to try (and only one of them will work). $\endgroup$ – Eric Towers Mar 9 '14 at 2:52
  • $\begingroup$ so if I substitute 3 in $b_1$ I would have $ 6 \equiv 1$ mod 7.. so divide 6 by 7? would that be it? $\endgroup$ – usukidoll Mar 9 '14 at 2:56
  • $\begingroup$ If you saw the equation "$6=1$", would you think "true" or false"? When you see the congruence "$6 \cong 1 \mod 7$", do you think "true" or "false"? $\endgroup$ – Eric Towers Mar 9 '14 at 2:59
2
$\begingroup$

The innocent way. Reduce your work with the $\mathrm{\color{Red}{red}}$ equivalence between congruence systems.

$$\begin{cases} x\equiv 2\pmod 7 \\ x\equiv 5 \pmod 6 \\ x \equiv 2 \pmod 5 \end{cases}\color{Red}{\iff}\begin{cases} x\equiv 2\pmod {35} \\ x\equiv 5 \pmod 6 \end{cases}$$

From the first congruence, $x=35t+2$ for some $t$. This implies $$35t+2\equiv 2-t\equiv5\pmod 6\iff t\equiv 3\pmod 6.$$ Therefore, $t=6u+3$ for some $u$. All the solutions are then of the form $$x=35t+2=35(6u+3)+2=210u+107.$$ The least positive solution is $x_0=107.$

$\endgroup$
  • $\begingroup$ did you just solve for u? And, let's see $35t+2 \equiv 2 -t \equiv 5$ (mod 6 ) $ 6 \times 5 = 30... 35-30 = 5$ which is the remainder $Z_6 = [0,1,2,3,4,5]$ I have 4 O_O $\endgroup$ – usukidoll Mar 9 '14 at 3:24
  • $\begingroup$ @usukidoll Sorry, but I don't understand what you are trying to say. I'll try to clarify some things, though: the $$35t+2\equiv 2-t \pmod 6$$ step happens because $35t\equiv 36t - t\equiv -t\pmod 6$. Also, I did not solve for $u$. There is a whole family of solutions, and I picked the least positive one. The family is all integers of the form $210u + 107$ for $u\in\Bbb Z$. Choosing $u=0$ gives us the least positive one, $107$. $\endgroup$ – Ian Mateus Mar 9 '14 at 3:30
  • $\begingroup$ Alright, but I still don't understand $b_1 = 4$. Where did they get the 4 in this problem? $\endgroup$ – usukidoll Mar 9 '14 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.