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

• You "only" have to check the divisors of $2016$. Nov 30, 2017 at 19:37
• what do you mean? Nov 30, 2017 at 19:37
• A $k$ with the desired property must divide $2016$ because the trailing coefficient of a product of polynomials is the product of the trailing coefficients. Nov 30, 2017 at 19:39
• @Skrrrrrtttt: if $x^2-x+k$ is a divisor of $x^{135}+x+2016$ for every $x\in\mathbb{N}$ in particular that holds for $x=0$, hence $k$ is a divisor of $2016$. Evaluating at $x=1$ you get that $k$ has to be a divisor of $2018$, too, so there are not so many chances, and they are simple to rule out. Nov 30, 2017 at 19:39
• cant you just say that if kr=2016 and kr=2018 this is a contradiction since a the product of k and r cannot equal the same thing? Nov 30, 2017 at 19:45

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

• why does it have to make it even? Nov 30, 2017 at 20:46
• @Skrrrrrtttt the "even" in last sentence doesn't refer to even-oddness of number. it is used as an adverb "used to emphasize something surprising or extreme." Nov 30, 2017 at 23:32

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

• so essentially you show that g(x) is irreducible and cannot be divided by any other polynomial? Nov 30, 2017 at 20:17