<s>[INST] find all $k$ such that $k^5+3$ is divisible by $k^2+1$ That's it. I have a solution with substitutions, but it's tedious and not too generic. Is there a solution using some cool theorem for polynomials divisibility?
 [/INST] Solution with substitutions.
If $k^5+3$ is divisible by $k^2+1$, it could be expressed as $(k^2+1)(k^3+n)$, which if expanded, leads us to $k^3+nk^2+n-3$.
Now let's make another substitution by introducing another variable $a: k=-(n+a)$, which will get us $-an^2+(1-2a^2)n-(a^3+3)$. It is solvable for $n$ only when $D\ge0$ or $-4a^2-12a+1\ge0$.
Roots of the last [expression turned into an] equation are $-3\pm\frac{\sqrt{10}}{2}$, and since we are looking only for integers, we need to check $a\in\{-3,-2,-1,0\}$.
Now we can start unrolling our substitutions. For all valid values of $a$, solve $-an^2+(1-2a^2)n-(a^3+3)$ for $n$, and get values of $k$ directly as $-(n+a)$
$$\begin {array} {r|r} \ equation & a & n & k\\
\hline
3n^2-17n+24=0 & -3 & 3 & 0 \\
3n^2-17n+24=0 & -3 & \frac83 & - \\
2n^2-7n+5=0 & -2 & 1 & 1 \\
2n^2-7n+5=0 & -2 & 2.5 & - \\
n^2-n-2=0 & -1 & -1 & 2 \\
n^2-n-2=0 & -1 & 2 & -1 \\
n-3=0 & 0 & 3 & -3 \\
\end {array}$$
</s>