I recently encountered the following story on Stack Exchange:
In 1969, D. J. Lewis wrote a paper about Diophantine equations, in which he wrote that the equation \(x^3 + 5 = 117 y^3\) is known to have at most 18 solutions, but the exact number is not known. Two other mathematicians studied the equation and, in 1971, they published a short but difficult proof that there are no solutions. Finally, in 1973, another mathematician found an astonishingly simple proof of the same fact! The proof is:
The quantity \(x^3 + 5\) is never a multiple of 9, but the quantity \(117 y^3\) is always a multiple of 9, so there are no solutions.
I decided to try to verify the short proof at the end of this amusing anecdote. It is easy to show that \(117 y^3\) is always a multiple of 9, because 117 is a multiple of 9. It is somewhat less obvious that \(x^3 + 5\) is never a multiple of 9. This statement is equivalent to \(x^3 \not\equiv 4\ (\text{mod}\ 9)\). I couldn’t come up with an easier way to prove this than just checking all 9 congruence classes individually.
We have:
- \(0^3 \equiv 0\ (\text{mod}\ 9)\)
- \(1^3 \equiv 1\ (\text{mod}\ 9)\)
- \(2^3 \equiv 8\ (\text{mod}\ 9)\)
- \(3^3 \equiv 0\ (\text{mod}\ 9)\)
- \(4^3 \equiv 1\ (\text{mod}\ 9)\)
- \(5^3 \equiv 8\ (\text{mod}\ 9)\)
- \(6^3 \equiv 0\ (\text{mod}\ 9)\)
- \(7^3 \equiv 1\ (\text{mod}\ 9)\)
- \(8^3 \equiv 8\ (\text{mod}\ 9)\)
When I wrote this out, I noticed an interesting pattern. If we evaluate \(a^3\ \text{mod}\ 9\) for \(a = 0,1,2,\dots\), we get a repeating cycle of \([0, 1, 8]\). This made me wonder whether this was a coincidence or if there was something more here. There are of course many well-known theorems about congruences of integer powers, such as Fermat’s little theorem, but I wasn’t familiar with this cyclic behavior.
To look for more general patterns, I wrote a Python script that uses matplotlib to graph the value of \(a^b\ \text{mod}\ m\) for different values of \(a\), \(b\), and \(m\). Each subplot graphs the values of the function for a single \(m\) value. The x-axis is (congruence classes of) \(a\), while the y-axis is \(b\). Columns where \(a\) is coprime to \(m\) are shown in black and white, while columns where \(a\) shares a factor with \(m\) are shown in color. The 3-cycle descibed above is visible as a repeating pattern of 3 colors in the row fourth from the bottom in the plot for \(m = 9\).
I noticed that there was also a repeating cycle of 5 elements with \(b = 5, m = 25\), similar to the previous repeating cycle with \(b = 3, m = 9\).
As it turns out, this pattern generalizes beyond \(9 = 3^2\) and \(25 = 5^2\). I was able to prove the following:
Theorem: \(a^b\ \text{mod}\ b^2\) is \(b\)-periodic in \(a\). In other words, \((a+b)^b \equiv a^b\ (\text{mod}\ b^2)\).
Proof: By the binomial theorem, \((a + b)^b\) expands into a sum of monomials \[\sum_{k = 0}^{b} \binom{b}{k}\,a^{b - k}\,b^k.\] Any term with \(k \ge 2\) will be divisible by \(b^2\) and hence will not contribute to the final sum. So the final result will be \[\binom{b}{0}\,a^{b - 0}\,b^0 + \binom{b}{1}\,a^{b - 1}\,b^1 = a^b + b\,a^{b - 1}\,b.\] The last term is also divisible by \(b^2\) and hence will not contribute to the final sum. So the final result is just \(a^b\).
Yay, math!
