# Thread: Modular Arithmetic- brain teezer- finding x

1. ## Modular Arithmetic- brain teezer- finding x

HeY ppl! I have a senario I need to solve but need some help from you guyz! I'm at like step 2!

The senario is: A band of 17 pirates stole a sack of coins. When they tried to divide them equally among them, 3 coins remained. In the brawl that followed, one pirate was killed. Again, they tried to divide the coins equally among themselves only to find 10 coins remaining. Another pirate was killed! Now, upon dividing the coins, none was left. What is the minimum number of coins that the pirates could have been distributing.

So far all i know is that you use the Chinese Remainder theorem and you get a set of equations... ->
x = 3mod17
x = 10mod16
x = 0mod15

Anyone know how to solve this?!

2. Originally Posted by carmz
x = 3mod17
x = 10mod16
x = 0mod15
I like to do these problems without using Chinese Remainder Theorem. Watch how.

Look at 2nd and 3rd equations. Add modulos 17 to first congruence seven times. And add modulos 16 to second congruence seven times. We get,
$\displaystyle x\equiv 122(\bmod 17)$
$\displaystyle x\equiv 122(\bmod 16)$
Since $\displaystyle \gcd(16,17)=1$ we can combine and get,
$\displaystyle x\equiv 122(\bmod 272)$

Thus, we are left with simply,
$\displaystyle x\equiv 122(\bmod 272)$ (1)
$\displaystyle x\equiv 0(\bmod 15)$ (2)

Look at (1) subtract the modulos 272 once and with (2) subtract modulos 15 ten times, to get,

$\displaystyle x\equiv -150(\bmod 272)$
$\displaystyle x\equiv -150(\bmod 15)$

Since $\displaystyle \gcd(272,15)=1$ we can combine to get,
$\displaystyle x\equiv -150(\bmod 4080)\implies x\equiv 3930(\bmod 4080)$

3. How did you get the 122? And how did u know to add modulos 17 to first congruence and modulos 16 to second congruence exactly seven times? And thanks for helping with this btw! Ur a genius lolz!

4. Originally Posted by carmz
How did you get the 122? And how did u know to add modulos 17 to first congruence and modulos 16 to second congruence exactly seven times? And thanks for helping with this btw!
The thing is adding a modulus does not change the congruence.
If $\displaystyle x\equiv 3(\bmod 17)$ then $\displaystyle x\equiv 3 + 17 (\bmod 17)$ also, and so $\displaystyle x\equiv 3 + 2\cdot 17(\bmod 17)$. Thus, the point is you can keep on adding that modulos as much as you want without changing the congruence.

$\displaystyle x\equiv 3(\bmod 17)$
$\displaystyle x\equiv 10(\bmod 16)$

Your goal is to add to the first congruence $\displaystyle 17$ and $\displaystyle 16$ to the second enough times so that the numbers match. The problem is of course figuring out how many times to do it.

The first step is to gaze at the problem. Maybe you can mentally figure out how to do it, either by adding or subtracting. In this case it is not so clear.

If that fails I recommend to do it algebraically. Suppose you are adding 17 $\displaystyle x$ times and 16 [/tex]y[/tex] times. We want that $\displaystyle 3+17x = 10+16y \implies 17x - 16y = 7$. Now we need to find values $\displaystyle x,y$ (integers) which make this true. This is a linear Diophantine equation (did you study those). Note $\displaystyle 17(1) - 16(1) = 1\implies 17(7) - 16(7) = 6$. Thus, $\displaystyle x=7$ and $\displaystyle y=7$. And there, you go it.

The second times after I combined the congruences and was left with just two I was able to see mentally. Which saves times. And then you combine them and get your answer.

5. Hello, carmz!

This can be solved with ordinary algebra . . . and some imagination.

A band of 17 pirates stole a sack of coins.
When they tried to divide them equally among them, 3 coins remained.
In the brawl that followed, one pirate was killed.
Again, they tried to divide the coins equally among themselves and found 10 coins remaining.
Another pirate was killed! Now, upon dividing the coins, none was left.
What is the minimum number of coins that the pirates could have been distributing?
Let $\displaystyle N$ = original number of coins.

We know that: .$\displaystyle N \;=\;17a + 3\:\text{ for some integer }a \;\;{\color{blue}[1]}.$

. . . . and that: .$\displaystyle N \;=\;16b + 10\:\text{ for some integer }b\;\;{\color{blue}[2]}$

. . . . and that: .$\displaystyle N \;=\;15c\:\text{ for some integer }c\;\;{\color{blue}[3]}$

Equating [3] and [2]: .$\displaystyle 15c \:=\:16b + 10 \quad\Rightarrow\quad c \:=\:\frac{16b+10}{15} \:=\:b + \frac{b+10}{15}$

Since $\displaystyle c$ is an integer, $\displaystyle b + 10$ is a multiple of 15: .$\displaystyle b+10\:=\:15k\quad\Rightarrow\quad b \:=\:15k-10$

. . Substitute into [2]: .$\displaystyle N \:=\;16(15k-10) + 10 \quad\Rightarrow\quad N\;=\;240k -150\;\;{\color{blue}[4]}$

Equating [1] and [4]: .$\displaystyle 17a + 3 \:=\:240k - 150\quad\Rightarrow\quad a \:=\:\frac{240k - 153}{17} \:=\:14k - 9 + \frac{2k}{17}$

Since $\displaystyle a$ is an integer, $\displaystyle k$ is a multiple of 17.
. . The least value is: .$\displaystyle k \,=\,17$

Substitute into [4]: .$\displaystyle N \;=\;240(17) - 150 \quad\Rightarrow\quad \boxed{N\;=\;3930}$