Given integers $a, b, n$, and $m$, how can I decide if there exist a polynomial $p(x)$ and integers $k$ and $c$ such that the following holds true over the integers?
$$(x^n + a)(x^m + b)p(x) = x^k + c$$
I noticed that for this to happen, we need a polynomial of the form $x^k + c$ that is divisible by both $x^n + a$ and $x^m + b$, but I don't know how to use necessary condition.
Maybe such polynomial $x^k + c$ exist only for very specific values of $a, b, n$, and $m$...
As Florian mentions in a comment the roots of $(x^n + a)(x^m + b)$ must be contained in the roots of $(x^k + c)$.
The $N$th roots of any number $z \in \mathbb{C}$ lie equally spaced along a circle in the complex plane with radius $|\sqrt[N]{z}|$. Therefore, if the $n$th roots of $-a$ and the $m$th roots of $-b$ are also the $k$th roots of $-c$, they must all lie on the same circle with radius $r = |\sqrt[n]{-a}| = |\sqrt[m]{-b}| = |\sqrt[k]{-c}| $. From which we can deduce $|a| = r^n, |b| = r^m$ and $|c| = r^k$.
Let's write $a,b,c$ as complex numbers, with $arg(a) = \alpha$, $arg(b) = \beta$ and $arg(c) = \gamma$ (Note that $\alpha, \beta, \gamma \in \{0,\pi\}$. Then our equation becomes
\begin{eqnarray} (x^n + r^n e^{i \alpha})(x^m + r^m e^{i \beta}) p(x) &=& (x^k + r^k e^{i \gamma}) \nonumber \\ \iff (x^n - r^n e^{i (\alpha + \pi)})(x^m - r^m e^{i (\beta + \pi)}) p(x) &=& (x^k - r^k e^{i (\gamma + \pi)}) \nonumber \\ \iff \left(x^n - \left[r e^{\frac{i (\alpha + \pi)}{n}}\right]^n \right) \left( x^m - \left[r e^{\frac{i (\beta + \pi)}{m}}\right]^m \right) p(x) &=& \left( x^k - \left[r e^{\frac{i (\gamma + \pi)}{k}}\right]^k \right) \nonumber \\ \end{eqnarray}
Next, we can apply the identity
$$ (x^N - y^N) = \prod_{j=0}^{N-1} \left( x - y e^{\frac{2 \pi i j}{N}} \right) $$
to factor our equation as
\begin{eqnarray} \prod_{u=0}^{n-1} \left(x - r e^{ \frac{i (\alpha + \pi)}{n}} e^{\frac{2 \pi i u}{n}} \right) \prod_{v=0}^{m-1} \left(x - r e^{ \frac{i (\beta + \pi)}{m}} e^{\frac{2 \pi i v}{m}} \right) p(x) &=& \prod_{w=0}^{k-1} \left(x - r e^{ \frac{i (\gamma + \pi)}{k}} e^{\frac{2 \pi i w}{k}} \right)\nonumber \\ \iff \prod_{u=0}^{n-1} \left(x - r e^{ \frac{i (\alpha + \pi + 2 \pi u)}{n}} \right) \prod_{v=0}^{m-1} \left(x - r e^{ \frac{i (\beta + \pi + 2 \pi v)}{m}} \right) p(x) &=& \prod_{w=0}^{k-1} \left(x - r e^{ \frac{i (\gamma + \pi + 2 \pi w)}{k}} \right)\nonumber \end{eqnarray}
From this is should be clear that each of the linear factors on the LHS must be equal to exactly one of the linear factors on the RHS, and this can only be the case when $k$ is a multiple of both $m$ and $n$.
Further, note that the RHS of our equation has no repeated factors, so the same must be true on the LHS. A repeated factor occurs if for any value of $ u = 0, \dots n-1$ and $v \in \{ 0,\dots m-1\}$ we have:
\begin{eqnarray} r e^{ \frac{i (\alpha + \pi + 2 \pi u)}{n}} &=&r e^{ \frac{i (\beta + \pi + 2 \pi v)}{m}}\nonumber \\ \iff \frac{i(\alpha +\pi + 2 \pi u)}{n} &\equiv& \frac{i(\beta +\pi + 2 \pi v)}{m} \text{ mod } 2 \pi \nonumber \\ \iff \frac{\alpha + 2 \pi u}{n} &\equiv& \frac{\beta + 2 \pi v}{m} \text{ mod } 2 \pi \nonumber \\ \end{eqnarray}
As long as this equivalence is never satisfied (and $|\sqrt[n]{-a}| = |\sqrt[m]{-b}| = |\sqrt[k]{-c}|$ and $m,n | k$), you can be certain that all the factors of $(x^n + a)$ and $(x^m + b)$ will appear precisely once as factors of $(x^n + c)$. Hence $p(x)$ will be a polynomial.... over $\mathbb{C}[X]$.