Putnam 2019, Problem A-1

Determine all possible values of the expression
\[A^3 + B^3 + C^3 - 3ABC\]
where \(A, B,\) and \(C\) are nonnegative integers.

Solution:
The answer is all nonnegative integers not congruent to 3 or 6 (mod 9). Let $X$ denote the given expression; we first show that we can make $X$ equal to each of the claimed values. Write $B = A + b$ and $C = A + c$, so that
$$X = (b^2 - bc + c^2)(3A + b + c).$$

By taking $(b,c) = (0,1)$ or $(b,c) = (1,1)$, we obtain respectively $X = 3A + 1$ and $X = 3A + 2$; consequently, as $A$ varies, we achieve every nonnegative integer not divisible by 3. By taking $(b,c) = (1,2)$, we obtain $X = 9A + 9$; consequently, as $A$ varies, we achieve every positive integer divisible by 9. We may also achieve $X = 0$ by taking $(b,c) = (0,0)$.

In the other direction, $X$ is always nonnegative: either apply the arithmetic mean-geometric mean inequality, or write $b^2 - bc + c^2 = (b - c/2)^2 + 3c^2/4$ to see that it is nonnegative. It thus only remains to show that if $X$ is a multiple of 3, then it is a multiple of 9. Note that $3A + b + c \equiv b + c$ (mod 3) and $b^2 - bc + c^2 \equiv (b + c)^2$ (mod 3); consequently, if $X$ is divisible by 3, then $b + c$ must be divisible by 3, so each factor in $X = (b^2 - bc + c^2)(3A + b + c)$ is divisible by 3. This proves the claim.

**Remark.** The factorization of $X$ used above can be written more symmetrically as
$$X = (A + B + C)(A^2 + B^2 + C^2 - AB - BC - CA).$$

One interpretation of the factorization is that $X$ is the determinant of the circulant matrix
$$\begin{pmatrix} A & B & C \\ C & A & B \\ B & C & A \end{pmatrix}$$
which has the vector $(1,1,1)$ as an eigenvector (on either side) with eigenvalue $A + B + C$. The other eigenvalues are $A + \zeta B + \zeta^2 C$ where $\zeta$ is a primitive cube root of unity; in fact, $X$ is the norm form for the ring $\mathbb{Z}[T]/(T^3 - 1)$, from which it follows directly that the image of $X$ is closed under multiplication. (This is similar to the fact that the image of $A^2 + B^2$, which is the norm form for the ring $\mathbb{Z}[i]$ of Gaussian integers, is closed under multiplication.)

One can also the unique factorization property of the ring $\mathbb{Z}[\zeta]$ of Eisenstein integers as follows. The three factors of $X$ over $\mathbb{Z}[\zeta_3]$ are pairwise congruent modulo $1 - \zeta_3$; consequently, if $X$ is divisible by 3, then it is divisible by $(1 - \zeta_3)^3 = -3\zeta_3(1 - \zeta_3)$ and hence (because it is a rational integer) by $3^2$.