2022 CGMO

Let the set $D=\{0,1,\dots ,p-1\}$, and let the polynomial $f(x)=(x-1)x(x+1)=x^3-x$. The congruence and congruence symbol “$\equiv$” in this question refer to congruence modulo $p$. For $k=0,1,2,3$, let $$B_k=\{b\in D\mid \text{there are exactly }k\text{ elements }a\in D\text{ such that }f(a)\equiv b\}.$$ Consider an element $b$ in $B_2$, i.e., there exist $a_1\not\equiv a_2$ such that $f(a_1)\equiv f(a_2)\equiv b$. In this case, $$0\equiv (a_1^3-a_1)-(a_2^3-a_2)=(a_1-a_2)(a_1^2+a_1{a}_2+a_2^2-1)\Rightarrow a_1^2+a_1{a}_2+a_2^2\equiv 1.$$ Thus, for $a_3=-a_1-a_2$, we have $a_3^2+a_3{a}_1+a_1^2=(a_1+a_2{)}^2-(a_1+a_2)a_1+a_1^2\equiv 1$, so it can be deduced that $f(a_3)\equiv f(a_1)\equiv b$, by the definition of $B_2$, $a_3$ is congruent to one of $a_1,a_2$, so either $a_2\equiv -2a_1$ or $a_1\equiv -2a_2$, assume the former, in this case, $a_1^2+a_1{a}_2+a_2^2\equiv 3a_1^2\equiv 1$, $3b\equiv 3a_1^3-3a_1\equiv -2a_1$. When 3 is a quadratic residue modulo $p$, $a_1$ has two solutions; when 3 is not a quadratic residue modulo $p$, $a_1$ has no solution. Therefore, there are exactly $1+(\frac{3}{p})$ solutions for $a_1$, and the corresponding $b$ also has $1+(\frac{3}{p})$ solutions, i.e., $|B_2|=1+(\frac{3}{p})$. $$\text{Obviously, }|B_1|+2|B_2|+3|B_3|=|D|=p.$$ On the other hand, consider the pairs $(u,v)$ that satisfy "$f(u)\equiv f(v)$ and $u\not\equiv v$" (called a collision). This is equivalent to $u^2+uv+v^2\equiv 1$ and $u-v\not\equiv 0$. After changing variables to $(x,y)\equiv (\frac{u-v}{2},\frac{u+v}{2})$ (i.e., $(u,v)\equiv (x+y,y-x)$, such that $(x,y)$ and $(u,v)$ correspond one-to-one), it is transformed into $x^2+3y^2\equiv 1$ and $x\not\equiv 0$. We consider the number of $(x,y)$ pairs satisfying $x^2+3y^2\equiv 1(\mathrm{mod}p)$ (i.e., $(3y{)}^2\equiv 3-3x^2$). $$\begin{array}{rl}T& =\sum _{x=1}^{p}1+\left(\frac{3-3x^2}{p}\right)=p+\left(\frac{-3}{p}\right)\sum _{x=1}^p\left(\frac{x^2-1}{p}\right)=p+\left(\frac{-3}{p}\right)\sum _{x=2}^p\left(\frac{\frac{x+1}{x-1}}{p}\right)\\ & =p+\left(\frac{-3}{p}\right)\sum _{x=1}^{p-1}\left(\frac{1+\frac{2}{x-1}}{p}\right)=p+\left(\frac{-3}{p}\right)\sum _{z=1}^{p-1}\left(\frac{z+1}{p}\right)=p-\left(\frac{-3}{p}\right).\end{array}$$ The above formula uses the fact that $z=\frac{2}{x-1}$ traverses the complete set of residues modulo $p$, and that ${\sum }_{k=1}^p(\frac{k}{p})=0$. Among the $T$ pairs $(x,y)$, there are exactly $1+(\frac{3}{p})$ pairs for which $x\equiv 0$ (i.e., $3y^2\equiv 1$). Therefore, the number of ordered collision pairs $(u,v)$ is $$M=T-1-\left(\frac{3}{p}\right)=p-\left(\frac{-3}{p}\right)-1-\left(\frac{3}{p}\right)=T-|B_2|.$$ Thus, there are exactly $\frac{M}{2}$ unordered collision pairs $(u,v)$. Since the elements in $B_3$ correspond to 3 collisions, the elements in $B_2$ correspond to 1 collision, and the elements in $B_1$ and $B_0$ correspond to 0 collisions, it follows that $|B_2|+3|B_3|=\frac{M}{2}$. Thus, $|B_3|=\frac{M-2|B_2|}{6}$, so the number of all possible residues of $f(x)$ modulo $p$ is $$|B_1|+|B_2|+|B_3|=p-|B_2|-2|B_3|=p-\frac{M+|B_2|}{3}=p-\frac{T}{3}=\frac{2p+(\frac{-3}{p})}{3}=\lfloor \frac{2p+1}{3}\rfloor .$$

Note 1: Another way to calculate the number of solutions $T$ is: Consider the congruence equation $x^2+3y^2\equiv z^2$, which is equivalent to $3y^2\equiv z^2-x^2=(z+x)(z-x)$, having $p^2$ solutions ($y\equiv 0$ has exactly $2p-1$ solutions, $y\equiv 1$ has exactly $p-1$ solutions, and so on). The number of solutions with $z\equiv 0$ is $$m_0=1+(p-1)[1+\left(\frac{-3}{p}\right)],$$ and the number of solutions for the remaining $z\equiv 1,z\equiv 2,...,z\equiv p-1$ are equal (using $(x,y,z)\leftrightarrow (kx,ky,kz)$ to map the solutions with $z\equiv 1$ to the solutions with $z\equiv k$), each equal to $T=\frac{p^2-m_0}{p-1}=p-\left(\frac{-3}{p}\right)$. If one is not familiar with Legendre symbols, one can first obtain $0\le m_0\le 2p$, and deduce that the number of solutions to $x^2+3y^2\equiv 1$ is $T\in p-1,p,p+1$. The subsequent answer to this problem is $p-\frac{T}{3}$, which is an integer. From this, we can still get the needed answer. Note 2: Another interpretation of the number of solutions $T=p-\left(\frac{-3}{p}\right)$ is: For each $y$, the number of $x$ that satisfy $x^2\equiv 1-3y^2$ is $1+\left(\frac{1-3y^2}{p}\right)$, therefore $$\begin{array}{rl}T-p& =\sum _{y=0}^{p-1}\left(\frac{1-3y^2}{p}\right)\equiv \sum _{y=0}^{p-1}(1-3y^2{)}^{\frac{p-1}{2}}\\ & =\sum _{y=0}^{p-1}\left({\left(-3\right)}^{\frac{p-1}{2}}{y}^{p-1}+\cdots +1\right)\equiv (-3{)}^{\frac{p-1}{2}}(p-1)=-\left(\frac{-3}{p}\right).\end{array}$$