Polynomial and divisibility

Find an integer polynomial $P(x)$ with the lowest degree that satisfies the following:

$P(x)$ is divisible by $x^2+x+1$

$P(x)+3$ is divisible by $x^{2017} -1$

Solution

Let $Q(x) = x^2+x+1$ and $R(x) = x^{2016} + \dots + 1$. It's easy to show that $Q$ and $R$ are relatively prime.

The LCM for both divisors is thus $(x-1)Q(x)R(x)$ which has degree 2019.

Now if $P$ and $P'$ both satisfy the problem statement, then $P-P'$ must be divisible by $(x-1)Q(x)R(x)$.

On the other hand, if $P$ satisfies the problem statement, then $P + A(x).(x-1)Q(x)R(x)$ also satisfies the problem statement for any integer polynomial $A(x)$.

Therefore, we can find at most one $P(x)$ with degree less than 2019, because if there were two such polynomials, their difference must be divisible by $(x-1)Q(x)R(x)$ but that difference has degree less than 2019, so the difference must be zero. That one polynomial is our answer.

To find it: let $t$ be the root of $Q(x)$. We want to find $P(x)$ such that:

$$P(x)+3 = S(x).(x-1).R(x)$$ for some $S(x)$, with $S(x) = ax+b$. We know that it's possible for $S$ to be a linear function because we've established that there exists a $P$ with degree less than 2019, and $R$ has degree 2016.

$$P(t) + 3 = (at+b).(t-1).R(t)$$

$P(t) = 0$ because $P(x)$ is divisible by $Q(x)$ and $Q(t) = 0$.

$R(t) = t^{2016} + \dots + t + 1 = 1$ because every 3 consecutive terms in $t^{2016} + \dots + t$ sum to zero (because $Q(t) = 0$).

So: $$ 3 = (at+b)(t-1)$$ $$at^2 + (b-a)t - b-3 = 0$$ $$a(-t-1) + (b-a)t - b-3 = 0$$ $$ (b-2a)t=a+b+3$$

Solving for the system:$b-2a = 0, a+b+3 = 0$ gives us: $a = -1, b= -2$ so $S(x) = -(x+2)$

Plugging in to the equations, we find:

$$P(x) = -(x+2)(x^{2017}-1) - 3 = -x^{2018} - 2x^{2017} + x -1 = -x^2(x^{2016}-1) -2x(x^{2016}-1) -( x^2+x+1) $$

Each term in the right-most expression is divisible by $Q(x)$ because $(x^{2016}-1)$ is divisible by $x^3-1$ so $P(x)$ is also divisible by $Q(x)$