How can you decide, if a polynomial with integer coefficients p(x) is the product (q(x))^2\*r(x) of two other polynomial with integer coefficients q(x), r(x)?



Polyomial roots
First of all, there is always the trivial factorization with $q=1$ and $r=p$. I'll discuss when more interesting ones exist, and how to find them. To make life simple, I'll deal with rational coefficients for most of the answer, and only address integrality at the end. 


To give a short answer first, there is a nontrivial factorization $p = q^2 r$ if and only if $GCD(p, \partial p/\partial x) \neq 1$.


Write $p = p\_1(x)^{1} p\_2(x)^{2} \cdots p\_k(x)^{k}$, where each $p\_j$ has distinct (complex) roots and where the roots of $p\_i$ and $p\_j$ are disjoint. In other words, factor $p$ over $\mathbb{C}$ and group together roots that occur the same number of times. Clearly, a nontrivial expression of $p$ as $q^2 r$ is possible if and only if one of the $p\_i$ is not $1$. I will explain the following points:


(1) There is a good algorithm to compute the $p\_i$ (much better than actually factoring $p$ over $\mathbb{Q}$!).
(2) Each $p\_i$ has rational coefficients.


The key to part (1) is the observation $GCD(p, \partial p/\partial x) = \prod p\_i^{i-1}$. 
To see this, notice that any root of the GCD must be a root of $p$. Moreover, if $r$ is a $k$-fold root of $p$ then it is a $(k-1)$-fold root of $\partial p/\partial x$. 


To compute the GCD, use [Euclid's algorithm for polynomials](http://en.wikipedia.org/wiki/Euclidean_algorithm#Polynomials). Note that, at every step, the polynomials have rational. coefficients, so the result does. Repeatedly using this method, one can compute:
$$s\_1 := p\_1^{1} p\_2^2 p\_3^3 \cdots p\_k^{k}$$
$$s\_2 := \phantom{p\_1^{1}} p\_2^1 p\_3^2 \cdots p\_k^{k-1}$$
$$s\_3 := \phantom{p\_1^{1} p\_2^1} p\_3^1 \cdots p\_k^{k-2}$$
up to
$$s\_k := \phantom{p\_1^{1} p\_2^1 p\_3^1 \cdots} p\_k$$
Then $p\_k=s\_k$, $p\_{k-1} = s\_{k-1}/p\_k^2$, $p\_{k-2} = s\_{k-2}/p\_{k-1}^2 p\_k^3$ and so forth.


If you want to do all of this with integer coeffients, then I suggest first solving the problem with rational coefficients. Once you find a factorization $p=q^2 r$, with $q(x)$ and $r(x)$ having rational coefficients, write $p=a p\_0$, $q=b q\_0$ and $r=c r\_0$, with $p\_0$, $q\_0$ and $r\_0$ [primitive polynomials](http://en.wikipedia.org/wiki/Gauss%2527s_lemma_%2528polynomial%2529). Then [Gauss's lemma](http://en.wikipedia.org/wiki/Gauss%2527s_lemma_%2528polynomial%2529) tells you that $p\_0 = q\_0^2 r\_0$, and you can always absorb the constant into the $r$.


