Sum of products of 3

Let $p>3$ be a prime number, and let $S={2,3,\dots,p-1}$ Let $X = \sum_{ i < j < k \in S} ijk$, prove that $X + 1$ is divisible by $p$.

Solution

Because $p$ is odd, let $p = 2m+1$. First we calculate $1^2 + \dots + (p-1)^2 \mod p$. We do this by realizing that $1^2 = (p-1)^2 \mod p, 2^2 = (p-2)^2 \mod p$ and so on. Every term will have a "pair", so the sum is: $$1^2 + \dots + m^2 + (m+1)^2 + \dots + (p-1)^2$$ $$\equiv 2 (1 + \dots + m^2) \mod p$$ $$\equiv m(m+1)(2m+1) \equiv 0 \mod p$$ because $2m+1 = p$. This means that $2^2 + \dots + (p-1)^2 \equiv -1 \mod p$

Next we calculate $1^3 + \dots + (p-1)^3 \mod p$. We do this by realizing that $p = 1 + (p-1) | 1^3 + (p-1)^3, p=2+(p-2) | 2^3+(p-2)^3$ and so on. Like above, each term will have a pair that it cancels out with. Thus $1^3 + \dots + (p-1)^3 \equiv 0 \mod p$, so $2^3 + \dots + (p-1)^3 \equiv -1 \mod p$.

Now we also have that $1+\dots + (p-1) \equiv 0 \mod p$, so $2 + \dots + (p-1) \equiv -1 \mod p$. From this, we have: $$2\sum_{i < j \in S} ij \equiv (-1)^2-(-1) \equiv 2 \mod p$$ $$\sum_{i < j \in S} ij \equiv 1 \mod p$$ because $p$ is odd.

Now, for any real numbers $a_1, \dots, a_n$, let us define the following variables: $$A = a_1 + \dots + a_n$$ $$B = \sum_{i < j} a_i a_j$$ $$C = \sum_{i \neq j } a_i^2 a_j$$ $$D = \sum_{i < j < k} a_i a_j a_k$$ $$E = a_1^2 + \dots + a_n^2$$ $$F = a_1^3 + \dots + a_n^3$$ Then we have: $$AB = (a_1+\dots+a_n)(a_1a_2 + a_1a_3 + \dots + a_{n-1}a_n) = C + 3D$$ The identity from middle to right is because for each $a_i$ in $A$, it's either paired with $a_ia_j$ or $a_j a_k$ in B. If it's paired with $a_i a_j$ then it would contribute towards $C$, otherwise it would contribute towards $3D$. Likewise, each term in $C$ and $3D$ can be traced back to $AB$. Each term $a_i^2 a_j$ in $C$ comes from $a_i$ in $A$ and $a_i a_j$ in $B$. Each term $3a_i a_j a_k$ in $3D$ comes from three sources: $a_i$ in $A$ and $a_j a_k$ in $B$ and its permutations. To further convince ourselves, $A$ has $n$ terms, and $B$ has $n(n-1)/2$ terms, so $AB$ has $n^2(n-1)/2$ terms. $3D$ has $n(n-1)(n-2)/2$ terms and $C$ has $n(n-1)$ terms, so altogether they have $n^2(n-1)/2$ terms.

Furthermore: $$C = a_1^2(A-a_1) + a_2^2(A-a_2) + \dots + a_n^2(A-a_n) = AE - F$$ So: $$3D = AB-C = F + AB-AE$$ This identity holds for any real numbers $a_i$, and it's based on pure algebraic manipulation. We can apply this identity to our set $S$. We already know that $F \equiv -1, A \equiv -1, B \equiv 1, E \equiv -1 \mod p$. From there, we have $3D \equiv -3 \mod p$, which means $(3D+3)$ is divisible by $p$. Because $p > 3$ then $D+1$ is divisible by $p$.