Counting coconuts

Suppose there are $M$ coconuts in the central pile when one of the pirates takes their turn. One coconut is given to the monkey, the rest are divided into seven equal piles, and six of the piles are returned to the central pile. Mathematically, this corresponds to the function: $f(M) = \tfrac{6}{7}(M-1)$. In other words, every time a pirate visits the central pile, the number of coconuts shrinks as $M\mapsto f(M)$.

After seven visits, the initial number of coconuts has shrunken to a (positive) number that is divisible by $7$. We can express this as:
\[
f^{(7)}(N) = f(f(f(f(f(f(f(N))))))) = 7k
\]Expanding this formula, it is a linear equation relating $N$ and $k$, which is:
\[
N=\frac{5764801 k+3261642}{279936}
\]The problem asks us to find the smallest $N$. This is equivalent to finding the smallest positive integer $k$ such that $N$ is an integer. This sort of problem is called a linear congruence equation and it can be solved using modular arithmetic. In Mathematica, the command is:

Reduce[5764801 k + 3261642 == 0, k, Modulus -> 279936]


It can also be solved using WolframAlpha. The smallest solution is $k=39990$, which leads to $N=823537$. That’s a lot of coconuts!

I’ll assume you already read the above solution. In order to understand where the solution comes from, we need to take a brief detour into the world of modular arithmetic…

Detour: modular arithmetic

I’ll illustrate the technique using a simpler example. Let’s find the smallest positive $k$ such that $\frac{5k+2}{3}$ is an integer. Put another way, we want $5k+2$ to be divisible by 3. This is written as:
\[
5k+2 \equiv 0 \pmod{3}
\]The only thing that matters when we’re working “modulo 3” is the remainder upon division by 3. For example, the numbers $\{\dots,-3,0,3,6,\dots\}$ are all equivalent to 0 mod 3 because they are divisible by 3. Likewise, the numbers $\{\dots,-2,1,4,7,\dots\}$ are all equivalent to 1 mod 3 because they have a remainder of 1 (i.e. they are of the form $3k+1$ for some integer $k$). When adding or multiplying numbers together, we can replace them by any equivalent numbers modulo 3 and this doesn’t change the result. So, for example:
\[
5k+2\equiv 0 \pmod{3}
\quad\text{is the same as solving}\quad
2k\equiv 1\pmod{3}
\]Naturally, because we’re working modulo 3, we only need to try $k=\{0,1,2\}$, and we find the solution is $k\equiv 2$. This means, of course, that we could have used any $k$ of the form $3m+2$ and it would have also worked. The smallest positive $k$ is therefore $k=2$, and this works; $5\times 2+2=12$, which is divisible by 3.

Let’s turn our attention to the question of solving $ak\equiv b \pmod{m}$. Here, $a$, $b$, $m$ are fixed, and we want to solve for $k$. This is called a linear congruence equation and it is a well-known concept in number theory. I’ll summarize the key results below.

First, note that there need not be any solutions at all! For example, $5k\equiv 2 \pmod{15}$ clearly has no solution, since $5k$ can only be equal to $\{0,5,10\}$ modulo 15. There can also be multiple solutions. For example, $4k\equiv 2 \pmod{6}$ has solutions $k\equiv 2$ or $k\equiv 5$. In general,

1. Let $g=\textrm{gcd}(a,m)$ (greatest common divisor). Then the equation $ak\equiv b\pmod{m}$ has a solution if and only if $g$ divides $b$.
2. If $k_0$ is a particular solution, then there are $g$ solutions in total, given by: $\left\{k_0,\, k_0+\frac{m}{g},\, k_0+\frac{2m}{g},\,\dots,\,k_0+\frac{(g-1)m}{g} \right\}$
3. The modified equation $(\tfrac{a}{g})k \equiv \tfrac{b}{g} \pmod{\tfrac{m}{g}}$ reduces to the case $g=1$ because $\textrm{gcd}(\tfrac{a}{g},\tfrac{m}{g})=1$ by definition. Consequently this modified equation has a unique solution, which can serve as $k_0$ for the original equation.
4. To solve the case $g=1$, Bézout’s Identity states that there must exist $s$ and $t$ such that $sa+tm=1$. Then, we have $bsa+btm=b$, which implies that $k_0 = bs$ solves our equation. Bézout’s Identity can be solved via the Extended Euclidean Algorithm.

Back to coconuts!

Our goal was to find the smallest positive integer $k$ such that $N=\frac{5764801 k+3261642}{279936}$ is also an integer. This amounts to solving the linear congruence equation
\[
5764801k+3261642 \equiv 0\pmod{279936}
\]Reducing and rearranging this is equivalent to:
\[
166081k \equiv 97590\pmod{279936}
\]The first thing to observe is that $279936=2^7\cdot 3^7$ whereas $166081$ is a prime number. Therefore, $\mathrm{gcd}(166081,279936)=1$. So we know the linear congruence has a unique solution. The solution to the Bézout Identity can be computed using the Mathematica function:
{g, {s, t}} = ExtendedGCD[166081, 279936].
This yields the result:
\[
(123073)(166081)+(-73017)(279936)=1
\]So the solution is $k\equiv 97590 \cdot 123073 \equiv 39990\pmod{279936}$. We can now compute $N$ as:

$\displaystyle
N=\frac{5764801\cdot 39990 +3261642}{279936} = 823537
$

If we want to find all solutions, we can add multiples of $279936$ to the base $k_0$ we found. This yields a solution set of the form:
\[
N = 823537 + 5764801m\qquad\text{for: }m=0,1,2,\dots
\]