Q:
Determine all possible values of the expression
\[ A^3+B^3+C^3−3ABC \]
where \(A\), \(B\), and \(C\) are nonnegative integers.
A:
Hello from 2020! I recently spent the Christmas break in Chicago, where I was able to have a few in-person math sessions with our very own Franklin Lu. Needless to say, we had a prolific time.
The first post of this year iterates an important lesson for us all: don’t let any problems ever intimidate you, even if they come from this year’s Putnam. That and the fact that you should always examine integers cubed \(\pmod 3\).
We begin this problem by trying to generate as small of numbers as possible from the given expression. The intuition behind this approach is that we want to see what “gaps” are left behind after we generate, say, all the possible expression values under 100. Upon initial examination of the expression, we note that if the value of \(A\) were to dominate \(B\) and \(C\), then the positive \(A^3\) term would dominate the negative \(3ABC\) term, and intuitively the value of the expression would be quite large (relative to \(A\), \(B\), and \(C\)). Thus, if we want to generate small numbers, then it makes sense to examine the cases where \(A\), \(B\), and \(C\) are very close to each other.
Remark 1
We can generate all positive non-multiples of \(3\).
Proof Remark 1
This first observation arises out of our examination of expression values where \(A\), \(B\), and \(C\) differ from each other by \(1\).
For any given \(A\), take \(B = C = A+1\). Then our expression evaluates as follows:
\[ A^3+B^3+C^3−3ABC = A^3 + (A+1)^3 + (A+1)^3 - 3A(A+1)^2 \]
\[ = 3A^3 + 6A^2 + 6A + 2 - 3A^3 - 6A^2 - 3A \]
\[ = 3A + 2 \]
Since \(A\) can be any nonnegative integer, this shows us that we can generate all positive integers that are equivalent to \(2 \pmod 3\).
In similar fashion, we can also take \(B = A\) and \(C = A+1\). In this case, we have:
\[ A^3+B^3+C^3−3ABC = A^3 + A^3 + (A+1)^3 - 3A^2(A+1) \]
\[ = 3A^3 + 3A^2 + 3A + 1 - 3A^3 - 3A^2 \]
\[ = 3A + 1 \]
which shows us that we can also generate all positive integers that equivalent to \(1 \pmod 3\). Thus we can generate all posivite non-mulitples of \(3\).
The question remains whether or not we can also generate all multiples of \(3\). It turns out that we cannot:
Remark 2
If \(A^3+B^3+C^3−3ABC\) is divisible by \(3\), then it must also be divisible by \(9\).
Proof Remark 2
Suppose \(A^3+B^3+C^3−3ABC\) is divisible by \(3\). Then we have
\[ 0 \equiv A^3+B^3+C^3−3ABC \equiv A + B + C \pmod 3 \]
(Note that for all integers, \(A^3 \equiv A \pmod 3\). This is a special case of Fermat’s Little Theorem, but can be very easily illustrated by noting that there are only three possible residuals \(\pmod 3\) and cubing each residual yields itself.)
There are only a few ways that \(A\), \(B\), and \(C\) can satisfy \(A + B + C \equiv 0 \pmod 3\). Without loss of generality (due to the symmetry of \(A\), \(B\), and \(C\) in the expression), the only cases we must consider are
- \(A \equiv B \equiv C \pmod 3\).
- \(A \equiv 1\), \(B \equiv -1\), \(C \equiv 0 \pmod 3\).
If we assume Case 1, let \(r\) be the residual \(\pmod 3\) of \(A\), \(B\), and \(C\). We can then write
\[ A = 3a + r \] \[ B = 3b + r \] \[ C = 3c + r \]
for some nonnegative integers \(a\), \(b\), and \(c\). We have
\[ A^3+B^3+C^3−3ABC = (3a + r)^3 + (3b + r)^3 + (3c + r)^3 - 3(3a + r)(3b + r)(3c + r) \]
Here we note that in the binomial expansion
\[ (3a + r)^3 = (3a)^3 + 3(3a)^2r + 3(3a)r^2 + r^3 \]
every term except for the \(r^3\) term is a multiple of \(9\). Thus we see that \((3a + r)^3 \equiv r^3 \pmod 9\).
Additionally, we also note that
\[ 3(3a + r)(3b + r)(3c + r) = (9a + 3r)(3b + r)(3c + r) \equiv 3r(3b + r)(3c + r) \] \[ = (9rb + 3r^2)(3c + r) \equiv 3r^2(3c + r) \] \[ = 9r^2c + 3r^3 \equiv 3r^3 \pmod 9 \]
Thus
\[ A^3+B^3+C^3−3ABC \equiv r^3 + r^3 + r^3 - 3r^3 = 0 \pmod 9 \]
If we assume Case 2, then we can write
\[ A = 3a + 1 \] \[ B = 3b - 1 \] \[ C = 3c \]
And similarly to Case 1, we have
\[ A^3+B^3+C^3−3ABC \equiv 1^3 + (-1)^3 + 0^3 - 3(3c)(3a + 1)(3b - 1) \equiv 1 - 1 - 0 = 0 \pmod 9 \]
And thus we see that if the expression generates a multiple of \(3\), the generated value must in fact be a multiple of \(9\).
We are not quite finished, as we are now left with the question of whether or not the expression generates all multiples of \(9\). The answer to this question is yes, and once proved, we will finally be done.
Remark 3
We can generate all multiples of \(9\).
Proof Remark 3
The proof of this observation comes, once again, from our examination of values generated by \(A\), \(B\), and \(C\) which are close to each other.
Take
\[ A = B - 1 \] \[ C = B + 1 \]
Then we have
\[ A^3+B^3+C^3−3ABC = (B - 1)^3 + B^3 + (B + 1)^3 - 3(B - 1)B(B + 1) \] \[ = (B^3 - 3B^2 + 3B - 1) + B^3 + (B^3 + 3B^2 + 3B + 1) - 3B(B^2 - 1) \] \[ = 3B^3 + 6B - 3B^3 + 3B \] \[ = 9B \]
Which proves that we can generate all nonnegative multiples of \(9\).
Putting it all together
We conclude that the span of all values generated by \(A^3+B^3+C^3−3ABC\) can be written exactly as the union of three disjoint sets:
\[ \lbrace 3n + 1 : n \in \mathbb{Z}^+ \rbrace \cup \lbrace 3n + 2 : n \in \mathbb{Z}^+ \rbrace \cup \lbrace 9n : n \in \mathbb{Z}^+ \rbrace \]