51st IMO Shortlisted Problems

a. We show that the pair $(1,-51^2)$ is $51$-good but not very good. Let $P(x)=x^3-51^{2}x$. Since $P(51)=P(0)$, the pair $(1,-51^2)$ is not $n$-good for any positive integer that does not divide $51$. Therefore, $(1,-51^2)$ is not very good.

On the other hand, if $P(m)\equiv P(k)(\mathrm{mod}51)$, then $m^3\equiv k^3(\mathrm{mod}51)$. By Fermat's theorem, from this we obtain $$m\equiv m^3\equiv k^3\equiv k(\mathrm{mod}3)\text{and}m\equiv m^{33}\equiv k^{33}\equiv k(\mathrm{mod}17).$$ Hence we have $m\equiv k(\mathrm{mod}51)$. Therefore $(1,-51^2)$ is $51$-good.

b. We will show that if a pair $(a,b)$ is $2010$-good then $(a,b)$ is $67^i$-good for all positive integer $i$.

Claim 1. If $(a,b)$ is $2010$-good then $(a,b)$ is $67$-good.

Proof. Assume that $P(m)\equiv P(k)(\mathrm{mod}67)$. Since $67$ and $30$ are coprime, there exist integers $m^{\prime }$ and $k^{\prime }$ such that $k^{\prime }\equiv k(\mathrm{mod}67)$, $k^{\prime }\equiv 0(\mathrm{mod}30)$, and $m^{\prime }\equiv m(\mathrm{mod}67)$, $m^{\prime }\equiv 0(\mathrm{mod}30)$. Then we have $P(m^{\prime })\equiv P(0)\equiv P(k^{\prime })(\mathrm{mod}30)$ and $P(m^{\prime })\equiv P(m)\equiv P(k)\equiv P(k^{\prime })(\mathrm{mod}67)$, hence $P(m^{\prime })\equiv P(k^{\prime })(\mathrm{mod}2010)$. This implies $m^{\prime }\equiv k^{\prime }(\mathrm{mod}2010)$ as $(a,b)$ is $2010$-good. It follows that $m\equiv m^{\prime }\equiv k^{\prime }\equiv k(\mathrm{mod}67)$. Therefore, $(a,b)$ is $67$-good.

Claim 2. If $(a,b)$ is $67$-good then $67\mid a$.

Proof. Suppose that $67\nmid a$. Consider the sets $\{a{t}^2(\mathrm{mod}67):0\le t\le 33\}$ and $\{-3a{s}^2-b(\mathrm{mod}67):0\le s\le 33\}$. Since $a\not\equiv 0(\mathrm{mod}67)$, each of these sets has $34$ elements. Hence they have at least one element in common. If $a{t}^2\equiv -3a{s}^2-b(\mathrm{mod}67)$ then for $m=t\pm s$, $k=\mp 2s$ we have $$\begin{array}{rl}P(m)-P(k)=a(m^3-k^3)+b(m-k)& =(m-k)\left(a(m^2+mk+k^2)+b\right)\\ & =(t\pm 3s)\left(a{t}^2+3a{s}^2+b\right)\equiv 0(\mathrm{mod}67)\end{array}$$ Since $(a,b)$ is $67$-good, we must have $m\equiv k(\mathrm{mod}67)$ in both cases, that is, $t\equiv 3s(\mathrm{mod}67)$ and $t\equiv -3s(\mathrm{mod}67)$. This means $t\equiv s\equiv 0(\mathrm{mod}67)$ and $b\equiv -3a{s}^2-a{t}^2\equiv 0(\mathrm{mod}67)$. But then $67\mid P(7)-P(2)=67\cdot 5a+5b$ and $67\nmid 7-2$, contradicting that $(a,b)$ is $67$-good.

Claim 3. If $(a,b)$ is $2010$-good then $(a,b)$ is $67^i$-good for all $i\ge 1$.

Proof. By Claim 2, we have $67\mid a$. If $67\mid b$, then $P(x)\equiv P(0)(\mathrm{mod}67)$ for all $x$, contradicting that $(a,b)$ is $67$-good. Hence, $67\nmid b$.

Suppose that $67^i\mid P(m)-P(k)=(m-k)\left(a(m^2+mk+k^2)+b\right)$. Since $67\mid a$ and $67\nmid b$, the second factor $a(m^2+mk+k^2)+b$ is coprime to $67$ and hence $67^i\mid m-k$. Therefore, $(a,b)$ is $67^i$-good.