China Girls' Mathematical Olympiad

2013 is factorized as $2013=3\times 11\times 61$. Let $p_1=3$, $p_2=11$, $p_3=61$. We denote by $a_i$ the residue of $a$ modulo $p_i$, by $b_i$ the residue of $b$ modulo $p_i$ ($i=1,2,3$), $a,b\in \{1,2,\dots ,2013\}$. By the Chinese Remainder Theorem, we have a bijection of $(a,b)$ with $(a_1,a_2,a_3,b_1,b_2,b_3)$.

Now, let $f_i(x)=a_i{x}^3+b_{i}x$, $i=1,2,3$. We call a polynomial "good modulo $n$" if the residues of $f(0),f(1),\dots ,f(n-1)$ modulo $n$ are all distinct.

If $f(x)=a{x}^3+bx$ is not good modulo $2013$, then there exists $x_1\not\equiv x_2(\mathrm{mod}2013)$ such that $f(x_1)\equiv f(x_2)(\mathrm{mod}2013)$. Suppose $x_1\not\equiv x_2(\mathrm{mod}{p}_i)$. Let $u_1$ and $u_2$ be the residues of $x_1$ and $x_2$ modulo $p_i$, respectively. Then $u_1\not\equiv u_2(\mathrm{mod}{p}_i)$ and $f_i(u_1)\equiv f_i(u_2)(\mathrm{mod}{p}_i)$, so $f_i(x)$ is not good modulo $p_i$.

If $f(x)=a{x}^3+bx$ is good modulo $2013$, then for every $i$, $f_i(x)$ is good modulo $p_i$. The reason is as follows. For any distinct pair $r_1,r_2\in \{0,1,\dots ,p_i-1\}$, there exist $x_1,x_2\in \{1,2,\dots ,2013\}$ such that $x_1\equiv r_1(\mathrm{mod}{p}_i)$ and $x_2\equiv r_2(\mathrm{mod}{p}_i)$ and $x_2\equiv x_2(\mathrm{mod}\frac{2013}{p_i})$. Now $f(x_1)\equiv f(x_2)(\mathrm{mod}\frac{2013}{p_i})$, but $f(x_1)\not\equiv f(x_2)(\mathrm{mod}2013)$, so $f(r_1)\not\equiv f(r_2)(\mathrm{mod}{p}_i)$.

Hence, we need to determine the number of good polynomials $f_i(x)$ modulo $p_i$.

For $p_1=3$, by Fermat's theorem, a good polynomial $$f_1(x)\equiv a_1{x}^3+b_{1}x\equiv (a_1+b_1)x(\mathrm{mod}3)$$ is equivalent to say that $a_1+b_1$ is not divisible by $3$. There are in total six such $f_1(x)$.

For $i=2,3$, if $f_i(x)$ is good modulo $p_i$, then for any $u$ and $v\not\equiv 0(\mathrm{mod}{p}_i)$, $f_i(u+v)\not\equiv f_i(u-v)(\mathrm{mod}{p}_i)$, i.e., $$f_i(u+v)-f_i(u-v)=2v[a_i(3u^2+v^2)+b_i]$$ is not divisible by $p_i$. If $a_i\ne 0$, the residues modulo $p_i$ of elements in the sets $A=\{3a_i{u}^2\mid u=0,1,\dots ,\frac{p_i-1}{2}\}$ and $B=\{(-b_i-a_i{v}^2)\mid v=1,2,\dots ,\frac{p_i-1}{2}\}$ do not coincide, and $|A|+|B|=p_i$. So $A\cup B$ forms a complete residue system modulo $p_i$. Their sum must be a multiple of $p_i$, i.e., $$\sum _{u=0}^{\frac{p_i-1}{2}}3a_i{u}^2+\sum _{v=1}^{\frac{p_i-1}{2}}(-b_i-a_i{v}^2)\equiv 0(\mathrm{mod}{p}_i).$$ Now, $1^2+2^2+\cdots +{\left(\frac{p_i-1}{2}\right)}^2=\frac{1}{6}\cdot \frac{p_i-1}{2}\cdot \frac{p_i+1}{2}\cdot p_i$ is a multiple of $p_i$, so $-\frac{p_i-1}{2}\cdot b_i$ is also a multiple of $p_i$. Hence, $b_i$ is divisible by $p_i$, i.e., exactly one of $a_i$, $b_i$ is $0$.

If $a_i=0,b_i\ne 0$, then $f_i(x)=b_{i}x$ is obviously good. There are $p_i-1$ such good polynomials.

If $a_i\ne 0,b_i=0$, then $f_i(x)=a_i{x}^3$. For $p_2=11$, by Fermat's theorem, $(x^3{)}^7=x^{21}\equiv x(\mathrm{mod}11)$, so for $x_1\ne x_2(\mathrm{mod}11)$ and $x_1^3\ne x_2^3(\mathrm{mod}11)$, $f_2(x)=a_2{x}^3$ is good. There are in total $10$ such polynomials.

For $p_3=61$, as $4^3=64\equiv 125=5^3(\mathrm{mod}61)$, $f_3(x)=a_3{x}^3$ cannot be good.

Therefore, the total number that we are looking for is $6\times (10+10)\times 60=7200$. $\square$