4
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ +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$. $\endgroup$ – Jyrki Lahtonen Jun 4 '15 at 17:40
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jun 4 '15 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.