The pirate law stipulates that, to divide the coins of a treasure, the captain must choose a group of pirates (excluding himself). Then, the captain must distribute the same number of coins to each of the pirates in this group, in such a way that it is not possible to give each of them any of the remaining coins (respecting the fact that each pirate receives the same amount). The remaining coins are then given to the captain. On Captain Barbarossa's ship, there are 100 pirates (excluding the captain). Barbarossa must divide a treasure that contains fewer than 1000 coins. If he chooses 99 pirates, he will be left with 51 coins, but if he chooses 77 pirates, he will be left with 29 coins.

a) How many coins does the treasure contain?

b) How many pirates should Barbarossa choose to end up with the maximum possible number of coins?
Solution

a) Let $N$ be the number of coins in the treasure. When Barbaroxa chooses 99 pirates to divide the $N$ coins, 51 coins are left for him, that is, he can divide $N-51$ coins among 99 pirates, or equivalently, the number $N-51$ is divisible by 99. In particular, the number $N-51+99=N+48$ is also divisible by 99.

Similarly, we can conclude that $N-29$ is divisible by 77. Therefore, the number $N-29+77=N+48$ is also divisible by 77. Since $N+48$ is divisible by 77 and 99, then $N+48$ is divisible by the least common multiple of 77 and 99, which is 693.

We conclude that $N+48$ is a multiple of 693 less than $1000+48=1048$, and thus $N+48=693$. That is, $N=645$.

b) Let $n$ be the number of pirates Barbaroxa chose. To divide the coins, Barbaroxa must divide the number $N=645$ by $n$, say $645=q n+r$, and he will be left with $r$ coins ($q$ and $r$ are natural numbers). Note that

$$
(q+1) n>q n+r=645 \geq q n
$$

From the inequality on the left, we have that $(q+1) 100 \geq(q+1) n>645$, and thus $q \geq 6$. Let's now analyze the possible values of $q$.

- If $q=6$: From the inequality on the left of (*), we get $n>645 / 7>92$. In this case, $r=645-6 n \leq 645-6(93)=87$ and, when $n=93, r=87$.
- If $q=7$: From the inequality on the left of (*), we get $n>645 / 8>80$. In this case, $r=645-7 n \leq 645-7(81)=78$ and, when $n=81, r=78$.
- If $q \geq 8$: From the inequality on the right of (*), we get $645 \geq q n \geq 8 n$, and thus $81>645 / 8 \geq n>r$.

From this analysis, we can conclude that Barbaroxa can obtain a maximum of $r=87$ coins. For this, he must choose $n=93$ pirates.