2010 IMO SL #N4

Let $a, b$ be integers, and let $P(x) = ax^3+bx.$ For any positive integer $n$ we say that the pair $(a,b)$ is $n$-good if $n | P(m)-P(k)$ implies $n | m - k$ for all integers $m, k.$ We say that $(a,b)$ is $very \ good$ if $(a,b)$ is $n$-good for infinitely many positive integers $n.$ 

(a) Find a pair $(a,b)$ which is 51-good, but not very good. 

(b) Show that all 2010-good pairs are very good.

(a) We claim that the pair $(1,-51^2)$ works. Let $P(x)=x^3-51^2x$. Then, because $P(51)=P(0)$, our pair is not $n$-good for any arbitrary positive integer $n$ that does not divide $51$. Hence it is not very good. 

We now show that it is $51$-good. If $P(m) \equiv P(k) \pmod{51}$, then $m^3 \equiv k^3 \pmod{51}$. By Fermat's Little Theorem, we have $$m \equiv m^3 \equiv k^3 \equiv k \pmod{3}$$ and $$m \equiv m^33 \equiv k^33 \equiv k \pmod{17}.$$

From these two we can deduce that $m \equiv k \pmod{51}$. Hence, our pair is $51$-good. 

We have shown the pair $(1,-51^2)$ that is $51$-good but is not very good. $\square$

(b) First, we claim that if a pair $(a,b)$ is $2010$-good, then it is $67$-good as well. So, we have $P(m)\equiv P(k) \pmod{67}$. Because $67,30$ are relatively prime, there exist integers $m',k'$ such that $k' \equiv k \pmod{67}$, $k' \equiv 0 \pmod{30}$, $m' \equiv m \pmod{67}$, and $m' \equiv 0 \pmod{30}$. Then, $P(m') \equiv P(0) \equiv P(k') \pmod{30}$ and $P(m') \equiv P(m) \equiv P(k) \equiv P(k') \pmod{67}$ Hence, we have $P(m')=P(k') \pmod{2010}$. This implies $m' \equiv k' \pmod{2010}$ by the $2010$-good condition. It then follows that $m \equiv m' \equiv k' \equiv k \pmod{67}$, as desired by our claim. 

Next, we claim that if $(a,b)$ is $67$-good, then $67 \mid a$. For the sake of contradiction assume $67 \nmid a$. Then, consider the sets $\left\{a t^{2}\pmod{67}: 0 \leq t \leq 33\right\}$ and $\left\{-3 a s^{2}-b\right.$ $\pmod{67}: 0 \leq s \leq 33\}$. Since $a \not \equiv 0 \pmod{67})$, each of these sets has 34 elements. Hence they have at least one element in common. If $a t^{2} \equiv-3 a s^{2}-b \pmod{67}$ then for $m=t \pm s, k=\mp 2 s$ we have

$$P(m)-P(k)=a\left(m^{3}-k^{3}\right)+b(m-k) =(m-k)\left(a\left(m^{2}+m k+k^{2}\right)+b\right)$$

$$=(t \pm 3 s)\left(a t^{2}+3 a s^{2}+b\right) \equiv 0 \quad \pmod{67}$$

Since $(a, b)$ is 67 -good, we must have $m \equiv k(\bmod 67)$ in both cases, that is, $t \equiv 3 s \pmod{67}$ and $t \equiv-3 s \pmod{67}$. This means $t \equiv s \equiv 0 \pmod{67}$ and $b \equiv-3 a s^{2}-a t^{2} \equiv 0 \pmod{67}$. But then $67 \mid P(7)-P(2)=67 \cdot 5 a+5 b$ and $67 \nmid 7-2$, contradicting that $(a, b)$ is $67$-good.

Lastly, we claim that if $(a,b)$ is $2010$-good, then $(a,b)$ is $67^i$-good for all $i \geq 1$. By our second claim, we have $67 \mid a$. If $67 \mid b$, then $P(x) \equiv P(0) \pmod{67}$ for all $x$, contradicting the fact that our pair is $67$-good. Thus $67 \nmid b$. Suppose that $$67^i \mid P(m)-P(k)=(m-k)(a(m^2+mk+k^2)+b).$$ Since $67 \mid a, 67 \nmid b$, the factor $a(m^2+mk+k^2)+b$ is relatively prime to $67$ and thus $67^i \mid m-k$. 

So, if a pair is $2010$-good, then it is $67^i$-good for all $i \geq 1$, which shows the desired. $\square$