Scroll To Bottom MathBin Diophantine Equation - Pirate's Treasure Member

Five pirates arrive at an island in search of buried treasure. A map leads them to a chest of siver coins, which they dig up and carry back to their ship. During the night, one pirate wakes up and takes his share of the treasure. He divides the coins into five equal piles, with one coin left. He hides his share along with the extra coin, and goes back to sleep.

The second pirate wakes up and does the same thing. After dividing the coins into five piles, one coin is left. He hides his share along with the extra coin, and goes back to sleep. The third, fourth, and fifth pirate commit the same devious deed. The next morning, after they all wake up, they divide the remaining coins into five equal shares, with no coins left over.

What is the smallest number of coins possible in the treasure chest?

Plunder
Split Count Share Pirate Total
1
2
3
4
5
6
   

Analysis

Let's call the original number of coins C1, where each Ci is the number of coins before each pirate takes his share. Because there is one coin left after each pirate divides the coins into five piles, the number of coins must be a multiple of five, plus 1. When the pirates divide the coins the next morning, the number of coins must be a multiple of five, since no coins are left. During the night, if pirate P1 took his share first, and pirate P5 took his share last, each pirate in turn got a smaller share of the coins.

Below is a table with the equal share each time the coins are divided.

Shares From First Split to Sixth Split
Share Remainder Note
S1 = (C1 - 1) / 5 C2 = 4 * S1 C1 is multiple of 5, plus 1
S2 = (C2 - 1) / 5 C3 = 4 * S2 C2 is multiple of 5, plus 1
S3 = (C3 - 1) / 5 C4 = 4 * S3 C3 is multiple of 5, plus 1
S4 = (C4 - 1) / 5 C5 = 4 * S4 C4 is multiple of 5, plus 1
S5 = (C5 - 1) / 5 C6 = 4 * S5 C5 is multiple of 5, plus 1
S6 = C6 / 5 0 C6 is multiple of 5

This table can be converted to a diophantine equation in terms of C5 and C0 by working backwards. The first step is easy, but each additional step gets more complicated. 

		5  C6 +    4 = 4  C5 = 4  [(4/5) (C4 - 1)]
		52 C6 +   20 = 42 C4 - 42
		52 C6 +   36 = 42 C4 = 42 [(4/5) (C3 - 1)]
		53 C6 +  180 = 43 C3 - 43
		53 C6 +  244 = 43 C3 = 43 [(4/5) (C2 - 1)]
		54 C6 + 1220 = 44 C2 - 44
		54 C6 + 1476 = 44 C2 = 44 [(4/5) (C1 - 1)]
		55 C6 + 7380 = 45 C1 - 45
		55 C6 + 8404 = 45 C1

The diophantine equation is 45 C1 - 55 C6 = 8404, where 45 = 1024 and 55 = 3125.

Another way to view this problem is to work backwards. From C6, which we know is a multiple of 5, S5 = C5 / 4. This means C6 is also a multiple of 4. The least common multiple of 4 and 5 is 20, so C6 is a multiple of 20. Below is a table that works backwards to the original number of coins in the chest.

Shares From Sixth Split to First Split
Share Coins Note
S6 = C6 / 5 C6 C6 is multiple of 5
S5 = C6 / 4 C5 = 5 * S5 + 1 C6 is multiple of 4
S4 = C5 / 4 C4 = 5 * S4 + 1 C5 is multiple of 4
S3 = C4 / 4 C3 = 5 * S3 + 1 C4 is multiple of 4
S2 = C3 / 4 C2 = 5 * S2 + 1 C3 is multiple of 4
S1 = C2 / 4 C1 = 5 * S1 + 1 C2 is multiple of 4