Given a prime $p$, show that there exist two integers $a, b$ which satisfies the following. For all integers $m$, $m^3+ 2017am+b$ is not a multiple of $p$.
Problem
Source: 2017 KMO Problem 5
Tags: number theory, polynomial, Cubic, Divisibility
CEH
12.11.2017 13:21
For korean contestant: Should I need to prove “law of quadratic reciprocity?”
rkm0959
12.11.2017 13:22
No. You don't need to prove it.
MarkBcc168
12.11.2017 13:25
If $p=2017$, the set $\{m^3\mid m=0,1,2,...,2016\}$ takes $\dfrac{2017-1}{3}=672$ residues in $\pmod p$. If $p=3$, take $a=2, b=1$ so we have $m^3+2017am+b\equiv m+2m+1\equiv 1\pmod p$. If $p\ne 2017, 3$, take $a=2017^{-1}$ and use this problem to conclude.
tenplusten
12.11.2017 14:16
Can you eloborate more please? I think APMO's problem is a bit different?
MarkBcc168
12.11.2017 14:19
So the APMO problem tell that if $p\ne 3$ then there are exists a positive integer $r$ such that $p\nmid x^3+x-r$ for every positive integer $x$. (You have to look at the answer of the APMO problem) Now just take $b=-r$ and we are done.
rkm0959
12.11.2017 16:04
For $p=2$, take $a=b=1$. For $p=3$, take $a=2, b=1$. For $p \equiv 1 \pmod{3}$, take $a=0$. We know that $f(x)=x^3$ is not injective (on $\pmod{p}$) since $(g^k)^3 \equiv (g^{2k})^3 \equiv 1 \pmod{p}$, where $g$ is a primitive root and $k=\frac{p-1}{3}$. Therefore, there is an $b$ such that $b \not\equiv -m^3 \pmod{p}$ for all integers $m$. Taking this $b$, we are done here. For $p \equiv 2 \pmod{3}$, since $(p,2017)=1$, take $a=-2017^{-1}$. Then denoting $f(m)=m^3+2017am$, we have $f(0) \equiv f(1) \equiv 0 \pmod{p}$, so $f(x)$ is not surjective again. Take $b$ so that $-b$ is not in the range of $f$, and we are done.
rafayaashary1
12.11.2017 16:19
Do the $p=3,2017$ cases separately (it is easy). We can count the number of reducible, monic trinomials over $\mathbb F_p$ whose roots sum to $0$ as strictly less than $p^2$ (the number of ways to choose a monic linear factor and an appropriate monic quadratic factor), since the case where the polynomial splits into not-all-identical linear factors is overcounted and there is at least one such cubic (e.g.: $(x-1)(x-1)(x+2)$). However, there are exactly $p^2$ distinct cubics of the form in the problem, so we conclude the result $\blacksquare$
S.C.B.
12.11.2017 18:06
Would I need to prove the existence of primitive roots?
PARISsaintGERMAIN
12.11.2017 21:47
S.C.B. wrote: Would I need to prove the existence of primitive roots? No, you don't need to.
RagvaloD
13.11.2017 00:18
Can we take such $a$ that $2017a\equiv -7 \pmod{p}$? Then $f(1)=1+2017a+b=b-6 \pmod{p}$ and $f(2)=8+2017a*2+b=b-6 \pmod {p}$ For $p=2017$: $2017=17^2+3*24^2=(17-24)^2+(2*24)^2+(17-24)*(2*24)$ so $(-7)^3 \equiv 48^3 \pmod {2017}$ and so we can take $a=0$ and $f(2010)=f(48) \pmod{2017}$
math90
13.11.2017 00:24
You have to consider $p=2017$ separately.
ayan.nmath
22.04.2018 11:08
2017 KMO Problem 5 wrote:
Given a prime $p$, show that there exist two integers $a, b$ which satisfies the following.
For all integers $m$, $m^3+ 2017am+b$ is not a multiple of $p$.
Solution.
We divide the proof into two cases,
Case (i). $p\ne 2017$
In this case choose $a\equiv 2017^{-1}(p-1)\pmod{p},$ then we want to choose $b$ such that $m^3-m\equiv -b\pmod{p}~\forall~m\in\mathbb N.$ Note that $0^3-0=1^3-1=0,$ therefore the set $A=\{m^3-m\pmod{p}\mid m=0,1,2,\ldots p-1\}$ has at least two repeated zeros, so there must exist an integer $c$ with is in $\{0,1,2,\ldots,p-1\}$ but not in $A,$ then taking $b\equiv -c\pmod p,$ we are done.
Case (ii). $p=2017$
Claim 1. The congruence $x^2\equiv -3\pmod{2017}$ has a solution in $x.$
Proof. It is equivalent to proving $\left(\frac{-3}{2017}\right)=1.$ Now,
\begin{align*}
\left(\frac{-3}{2017}\right)&=\left(\frac{-1}{2017}\right)\left(\frac{3}{2017}\right)\\
&=(-1)^{\tfrac{2017-1}{2}}\left(\frac{3}{2017}\right)\\
&=\left(\frac{3}{2017}\right)\\
&=(-1)^{\tfrac{2017-1}{2}\cdot\tfrac{3-1}{2}}\left(\frac{2017}{3}\right)^{-1}\\
&=\left(\frac{1}{3}\right)=1
\end{align*}Hence the claim. $\square$
Now choose $x$ such that $x\equiv y\cdot 2^{-1}(-1+\sqrt{-3})\pmod{2017}$ where $y\in\{1,2,3,\ldots,2016\}$, we know that $\sqrt{-3}\pmod{2017}$ is meaningful using Claim 1. Then observe that,
\begin{align*}
x^2+xy+y^2&\equiv \Big(y\cdot 2^{-1}(-1+\sqrt{-3})\Big)^2+\Big(y\cdot 2^{-1}(-1+\sqrt{-3})\Big)y+y^2\pmod{2017}\\
&\equiv y^2(-2)^{-1}(1+\sqrt{-3})+y^2 2^{-1}(-1+\sqrt{-3})+y^2\pmod{2017}\\
&\equiv y^2\left(2^{-1}(-1-\sqrt{-3}-1+\sqrt{-3})+1\right)\pmod{2017}\\
&\equiv 0\pmod{2017}
\end{align*}Therefore,
\[(x-y)(x^2+xy+y^2)\equiv 0\pmod{2017}\implies x^3\equiv y^3\pmod{2017}\]Since $x\equiv y\cdot 2^{-1}(-1+\sqrt{-3})\pmod{2017},$ it is not hard to verify that $x\not\equiv y\pmod p.$ Consider the set $B=\{m^3\pmod{2017}\mid m=1,2,3,\ldots,2016\},$ since we know that $\exists$ $x,y\not\equiv 0\pmod
{2017}$ with $x^3\equiv y^3\pmod {2017},$ hence there must exist an integer $k$ such that $k=1,2,3\ldots,2016$ and $k\not\in B.$ Now, choosing $b=2017-k,$ we are done. $\blacksquare$