Polyomial roots 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)?
 A: 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. 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. Then Gauss's lemma tells you that $p_0 = q_0^2 r_0$, and you can always absorb the constant into the $r$.
