What was the least number of coins that could have been stolen?

[Math100]

Homework Statement

(Ancient Chinese Problem.) A band of $17$ pirates stole a sack of gold coins. When they tried to divide the fortune into equal portions, $3$ coins remained. In the ensuing brawl over who should get the extra coins, one pirate was killed. The wealth was redistributed, but this time an equal division left $10$ coins. Again an argument developed in which another pirate was killed. But now the total fortune was evenly distributed among the survivors. What was the least number of coins that could have been stolen?

Relevant Equations

None.

Let $x$ be the least number of coins that could have been stolen.
Then $x\equiv 3\pmod {17}, x\equiv 10\pmod {16}$, and $x\equiv 0\pmod {15}$.
Applying the Chinese Remainder Theorem produces:
$n=17\cdot 16\cdot 15=4080$.
This means $N_{1}=\frac{4080}{17}=240, N_{2}=\frac{4080}{16}=255$ and $N_{3}=\frac{4080}{15}=272$.
Observe that
\begin{align*}
&240x_{1}\equiv 1\pmod {17}\implies 2x_{1}\equiv 1\pmod {17}\\
&\implies 18x_{1}\equiv 9\pmod {17}\implies x_{1}\equiv 9\pmod {17},\\
&255x_{2}\equiv 1\pmod {16}\implies -x_{2}\equiv 1\pmod {16}\\
&\implies x_{2}\equiv -15\pmod {16}\implies x_{2}\equiv 15\pmod {16},\\
&272x_{3}\equiv 1\pmod {15}\implies 2x_{3}\equiv 1\pmod {15}\\
&\implies 16x_{3}\equiv 8\pmod {15}\implies x_{3}\equiv 8\pmod {15}.\\
\end{align*}
Now we have $x_{1}=9, x_{2}=15$ and $x_{3}=8$.
Thus $x\equiv (9\cdot 3\cdot 240+15\cdot 10\cdot 255+0)\pmod {4080}\equiv 44730\pmod {4080}\equiv 3930\pmod {4080}$.
Therefore, the least number of coins that could have been stolen is $3930$.

 

[fresh_42]

Homework Statement:: (Ancient Chinese Problem.) A band of $17$ pirates stole a sack of gold coins. When they tried to divide the fortune into equal portions, $3$ coins remained. In the ensuing brawl over who should get the extra coins, one pirate was killed. The wealth was redistributed, but this time an equal division left $10$ coins. Again an argument developed in which another pirate was killed. But now the total fortune was evenly distributed among the survivors. What was the least number of coins that could have been stolen?
Relevant Equations:: None.

Let $x$ be the least number of coins that could have been stolen.
Then $x\equiv 3\pmod {17}, x\equiv 10\pmod {16}$, and $x\equiv 0\pmod {15}$.
Applying the Chinese Remainder Theorem produces:
$n=17\cdot 16\cdot 15=4080$.
This means $N_{1}=\frac{4080}{17}=240, N_{2}=\frac{4080}{16}=255$ and $N_{3}=\frac{4080}{15}=272$.
Observe that
\begin{align*}
&240x_{1}\equiv 1\pmod {17}\implies 2x_{1}\equiv 1\pmod {17}\\
&\implies 18x_{1}\equiv 9\pmod {17}\implies x_{1}\equiv 9\pmod {17},\\
&255x_{2}\equiv 1\pmod {16}\implies -x_{2}\equiv 1\pmod {16}\\
&\implies x_{2}\equiv -15\pmod {16}\implies x_{2}\equiv 15\pmod {16},\\
&272x_{3}\equiv 1\pmod {15}\implies 2x_{3}\equiv 1\pmod {15}\\
&\implies 16x_{3}\equiv 8\pmod {15}\implies x_{3}\equiv 8\pmod {15}.\\
\end{align*}
Now we have $x_{1}=9, x_{2}=15$ and $x_{3}=8$.
Thus $x\equiv (9\cdot 3\cdot 240+15\cdot 10\cdot 255+0)\pmod {4080}\equiv 44730\pmod {4080}\equiv 3930\pmod {4080}$.
Therefore, the least number of coins that could have been stolen is $3930$.

Correct, except for one step. You have $255x_{2}\equiv 1\pmod {16}\implies -x_{2}\equiv 1\pmod {16}$. Then multiplication with $-1$ yields $x_2\equiv -1 \equiv 15 \pmod{16}.$ This would be correct, but the step in between $\implies x_{2}\equiv -15\pmod {16}$ is not. If we had a single number with remainder $-1$ and $-15$ modulo $16$, then $-1-(-15)=14 \equiv 0 \pmod{16}$ which is a contradiction.

 

[Math100]

Correct, except for one step. You have $255x_{2}\equiv 1\pmod {16}\implies -x_{2}\equiv 1\pmod {16}$. Then multiplication with $-1$ yields $x_2\equiv -1 \equiv 15 \pmod{16}.$ This would be correct, but the step in between $\implies x_{2}\equiv -15\pmod {16}$ is not. If we had a single number with remainder $-1$ and $-15$ modulo $16$, then $-1-(-15)=14 \equiv 0 \pmod{16}$ which is a contradiction.

Yes, thank you for pointing that out. I was wrong about that.

 

[fresh_42]

Yes, thank you for pointing that out. I was wrong about that.

I only wanted to ensure you that I actually checked your proof.