The problem is to determine, whether there exist a quadratic trinomial $f(x) = ax^2 + bx +c$ with integer coefficients (with $a$ not a multiple of 2014), such that the numbers $\ f(1), \ f(2),\, \dots,\ f(2014)$ have different remainders when divided by 2014?

I have only basic training in the filed of algebra and do not even know how to approach the problem. I can refactor 2014 as $2014 = 2 \times 19 \times 53$, but that does not seem to help.

Write $2014 = 2N$, where $N = 1007$ is odd. I claim that

$$f(x) = N x^2 + 2 x = 1007 x^2 + 2x$$

has the required property.

Note that $f(x)$ is odd if $x$ is odd and even if $x$ is even. Hence, if $f(i)$ and $f(j)$ have the same remainder when divided by $2014 = 2N$, then $i$ and $j$ have the same parity, and so $i-j$ is divisible by $2$.

Suppose that $f(i)$ and $f(j)$ have the same remainder when divided by $2014 = 2N$. Then their difference is divisible by $2N$. Yet

$$f(i) - f(j) = N i^2 + 2i - N j^2 - 2j = N (i^2 - j^2) + 2 (i - j) = (N(i+j) + 2)(i - j).$$

The first factor $N(i+j) + 2$ is co-prime to $N$ (since $N$ is odd), and hence it follows that $f(i)-f(j)$ is divisible by $N$ if and only if $i-j$ is divisible by $N$. We have thus shown that if $f(i) - f(j)$ is divisible by $2N$, then $i-j$ is divisible by $2$ and $N$ and hence by $2N$. So we are done.

In fact, the only polynomials are $f(x) = 1007 x^2 + 2b x + c$ for some constant $b$ prime to $1007$, and these all work. Without giving the details, the key observations are:

1. By the Chinese Remainder Theorem, the condition in the problem is equivalent to $f(1), f(2), \ldots, f(p)$ all being distinct modulo $p$ for $p$ the prime factors of $2014$.

2. If a polynomial modulo $p$ has this property, then it has a unique root modulo $p$. However, any quadratic with one rational root has two rational roots, so either $f(x)$ is a constant times a square, or $f(x)$ is linear modulo $p$.

3. If $f(x)$ is a constant times a square modulo $p$, and $p > 2$, then the values $f(1), \ldots, f(p)$ are not distinct, because there are not enough quadratic residues modulo $p$.

• +1, but I want to make two remarks. A marginally simpler way to see that your polynomial works is to observe that the values of $g(x)=1007x^2+1007x$ are always divisible by $2014$, because $x^2+x$ is always even. Therefore for all integers $x$ we have $$f(x)\equiv f(x)-g(x)=-1005x\pmod{2014}.$$ From this the fact that $f$ induces a permutation of $\Bbb{Z}_{2014}$ is perhaps slightly more obvious. The choice $f_2(x)=1007x^2+1008x$ drives the point home in the sense that $f_2(x)\equiv x\pmod{2014}$ for all integers $x$. – Jyrki Lahtonen Jun 4 '15 at 17:40
• The other remark I want to make is that quadratic permutation polynomials like this play a role in the error-correcting-codes of the LTE cellular standard (also known as 4G). This Wikipedia article gives more information. – Jyrki Lahtonen Jun 4 '15 at 17:43