$x^4 + 1020x^3 - 4x^2 + 2039x+1$ is divisible by 1019.

Question

Give all integers x in the range [1,2018] such that $x^4 + 1020x^3 - 4x^2 + 2039x+1$

is divisible by 1019.

Applying mod 1019 to the coefficients, we have

$x^4 + x^3 - 4x^2 + x + 1$ which is equal to $(x-1)^2(x^2+3x+1)$

I tried making 1 of the factors equal to a multiple of 1019, but it looks tedious and i have not found a solution other than 1020.

answer given : 1, 492, 524, 1010, 1511, 1543

Answer 1

As $1019$ is prime, one of the factors must be $\equiv 0\pmod{1019}$. For $(x-1)$ this obviously means that $x=1$ or $x=1020$.

For the factor $x^2+3x+1$, we'd expect two solutions $x=\frac{-3\pm\sqrt{5}}2$ - but what is $\sqrt 5$ in modular arithmetic? Any $y$ with $y^2\equiv 5\pmod{1019}$. Fortunately, just playing with $1019+5=1024$, we see that $32^2\equiv5\pmod{1019}$. Hence $\frac{-3+32}{2}\equiv\frac{1016+32}{2}=524$ and $\frac{-3-32}{2}\equiv\frac{1016-32}{2}=492$ are remainders mod $1019$ that solve too (i.e., $492$, $524$, $1511$,$1543$)

Answer 2

$(x-1)^2(x^2+3x+1)\equiv0\bmod1019\implies$

$ x-1\equiv0\bmod1019$ or $x^2+3x+1\equiv0\bmod1019$.

The former implies $x\equiv1\bmod 1019$; solutions in $[1,2018]$ are $1$ and $1020$.

The latter implies $x^2+3x+\dfrac94\equiv\dfrac94-1\bmod1019$, so $\left(x+\dfrac32\right)^2\equiv9\times255-1\equiv256\bmod1019$,

so $x+\dfrac32\equiv\pm16,$ so $x\equiv\pm16-3(510)\equiv492 $ or $524$;

solutions in $[1,2018]$ are $492, 524, 1511$ and $1543$.