prove that there is no k such that $x^2-x+k$ divides $x^{135}+x+2016$ how would you prove that there exists no $k \in \Bbb{N}$ such that for all 
$x\in\Bbb{Z}$ the integer $x^2-x+k$ divides $x^{135}+x+2016$? I started off with contradiction by assuming that there exists a k such that $x^2-x+k$ divides $x^{135}+x+2016$
then $(x^2-x+k)r=x^{135}+x+2016$ for some $r \in \Bbb{Z}$ but from this point im finding it really hard to draw a contradiction.
 A: Assume the contrary that there is a $k \in \mathbb{N}$ such that
for all $x \in \mathbb{Z}$, there is a $r_x \in \mathbb{Z}$ such that 
$$x^{135} + x + 2016 = (x^2-x+k) r_k$$
For $x = 1, 0, -1$, we have
$$2018 = kr_1,\quad 2016 = kr_0\quad\text{ and }\quad 2014 = (2+k)r_{-1}$$
Since $k(r_1 - r_0) = 2018 - 2016 = 2$ and $k \in \mathbb{N}$, $k$ can only be $1$ or $2$. However,


*

*$k \ne 1$ because $k+2 = 3$ and $2014 \equiv 1 \not\equiv 0\pmod 3$.

*$k \ne 2$ because $k+2 = 4$ and $2014 \equiv 2 \not\equiv 0 \pmod 4$.


As a result, there is  no $k \in \mathbb{N}$ which can make $x^2 -x + k | x^{135} + x + 2016$, even only for these three $x$.
A: More can be said: there is no nonconstant polynomial $f(X)$ of degree $< 135$
with integer coefficients such that $f(x)$ divides $x^{135} + x + 2016$ for infinitely many integers $x$.
Let $g(X) = X^{135} + X + 2016$, and let $f(X) \in \mathbb Z[X]$ be a polynomial of degree $d$, $1 \le d < 135$.  Then there are $q(X), r(X) \in \mathbb Z[X]$ with $r(X)$ of degree $< d$ such that $g(X) = q(X) f(X) + r(X)$, and $f(x)$ divides $g(x)$ if and only if it divides $r(x)$.  Now since $r(X)$ has lower degree than $f(X)$, we have $|r(x)| < |f(x)|$ if $|x|$ is sufficiently large.
Thus the only way $f(x)$ can divide $g(x)$ for  infinitely many $x \in \mathbb Z$ is if $r(X) = 0$.  Thus
$f(X)$ would have to divide $g(X)$ as polynomials.  But it turns out
that $g(X)$ is irreducible over the rationals.  Therefore there is no such $f(X)$.
BTW: It's also true for $2017$ and $2018$, in fact for $X^{135} + X + y$ 
for all integers $y$ from $3$ to at least $3018$.
