Find The Product Mod P

I enjoyed this question. Here is my solution.

Notice that $( i^2 + ij + j^2 ) = \frac{ i^3 - j^3} { i-j}$ . This strongly suggests that we should look at $\prod (i-j)$ and $\prod (i^3 - j^3)$ .

Claim: $\{ i^3 \pmod{101} \} \equiv \{ i \pmod{101} \}$ .

Proof: As hinted by Sreejato, we will use the fact that $101 \equiv 2 \pmod{3}$ .
Suppose we have $a^3 \equiv b^3 \pmod{101}$ . By Fermat's Little Theorem, since 101 is prime, we know that $a^{100} \equiv b^{100}$ . Hence, we conclude that

$a \equiv a \times \left( a^{33} \right) ^3 = a^{100} \equiv b^{100} \equiv b \pmod{100}. _\square$

This shows that the map of $i \rightarrow i^3 \pmod{101}$ is one-to-one. Since they have the same cardinality, thus they are the same set.

Claim: Let $\rho (i) = i^3$ denote the permutation on the (non-zero) cubic residues mod 101. Then, the order of $\rho$ is odd.

Proof: Let $\omega$ be a primitive element of the non-zero residues mod 101. Then $\rho ( \omega ^k) = \omega^{3k}$ and so we have the map $\rho^* (k) = 3k$ on $\mathbb{Z} _{100}$ . By analyzing the orbits, we see that there are 11 cycles (with starting values of 0, 1, 2, 4, 5, 10, 11, 20, 25, 50, 55) hence, the order is 100-11 = odd. $_ \square$

As such,

$\prod_{1 \leq i \leq j \leq 100} ( i^3 - j^3) \pmod{101} = \prod_{1 \leq i \leq j \leq 100} ( \rho(i) - \rho(j) ) \pmod{101} \\ = sgn ( \rho) \times \prod_{ 1 \leq i \leq j \leq 100 } (i-j) = - \prod_{ 1 \leq i \leq j \leq 100 } (i-j)$

This allows us to conclude that

$\prod_{ 1 \leq i \leq j \leq 100 } ( i^2 + ij + j^2 ) \equiv -1 \equiv 100 \pmod{101}.$