Let $p, q \in \mathbb{Z}[x]$ be two integer-valued polynomial. Is there a (hopefully efficient) algorithm that checks whether $p^n = q^m$ for some $n,m \geq 1$?
I need such an algorithm for a program I have to write, but it seems that there isn't much information on the internet.
An idea is to take the leading coefficients $a$ and $b$ of $p$ and $q$ and then note that $p^n = q^m$ implies that $a^n = b^m$. The last equation can be solved using prime decompositions, and also gives that the set of solutions pairs (if any) are of the form $(k n_0, km_0)$, where $n_0, m_0 \geq 1$ are fixed and $k \geq 1$. Continuing with an inductive argument may work?
As TonyK mentioned in the comments, $p^n = q^m$ implies $n\deg p = m \deg q$, so $\frac{n}{m} = \frac{\deg q}{\deg p}$.
This means we can scale the exponents in the equation $p^n = q^m$ by raising to powers and/or taking roots of both sides to obtain
$$p^{\deg q} = \pm q^{\deg p} \tag{$*$}$$
where the $\pm$ comes from potentially taking an even root. So just compute both sides of $(*)$ and check if they're equal up to sign.
But, we can do better!
Raising polynomials to large powers is computationally expensive, so let's find a faster method.
Take the logarithmic derivative of both sides of $(*)$:
$$ \deg q \cdot \frac{p'}{p} = \deg p \cdot\frac{q'}{q}, $$
i.e.
$$ (\deg{q})\cdot p' q = (\deg{p}) \cdot q' p. \tag{$\dagger$}$$
So if $p^n = q^m$ for some $n$ and $m$, then $(\dagger)$ must hold, though the reverse is not necessarily true.
Reversing the steps, we see that if $(\dagger)$ is true, then $p^{\deg q} = C\cdot q^{\deg p}$ for some constant $C$. We want $C$ to be $\pm 1$; we can check if this is true from the leading coefficients $a$ and $b$. So we should have
$$a^{\deg q} = \pm b^{\deg p}. \tag{$\ddagger$}$$
In summary, $p^n = q^m$ for some $m$ and $n$ if and only if both $(\dagger)$ and $(\ddagger)$ hold.