polynomial GCD over $\mathbb{Z}[X]$

Question

Given two not necessarily monic polynomials in $\mathbb{Z}[X]$, how does one find their GCD in $\mathbb{Z}[X]$? I need to know in order to implement Yun's algorithm for square-free polynomial factorization, so presumably doing it by factoring the polynomials would defeat the purpose. I don't see how to use the Euclidean algorithm without getting coefficients outside of $\mathbb{Z}$ since $\mathbb{Z}$ isn't a field.

Maybe something like using the Euclidean algorithm over $\mathbb{Q}[X]$, then multiplying the result by the LCM of the denominators of the coefficients, and trying out different integer multiples of that?

Answer 1

To be more concrete about my questioning musing in the original post: if an integer can be factored out of the GCD of two polynomials, then that integer can also be factored out of those two polynomials, so the polynomial GCD takes the form of a polynomial whose coefficients are comprime times the GCD, $a$, of the coefficients of the original two polynomials, collectively. Therefore, it should suffice to apply the Euclidean algorithm over $\mathbb{Q}[X]$, then multiply away any coefficient denominators, then divide away any common integer factor of the coefficients, and finally multiply by $a$.

Answer 2

Every element $P$ of an UFD, $R$ factorizes uniquely $$ P=u\prod_{Q\in Irr(R)}Q^{\,\nu_Q(P)} $$ where $Irr(R)$ is a set of representatives of the irreducibles of $R$ and $u$ is a unit of $R$.

So, if
$$ P_1=u_1\prod_{Q\in Irr(R)}Q^{\,\nu_Q(P_1)}\ ;\ P_2=u_2\prod_{Q\in Irr(R)}Q^{\,\nu_Q(P_2)} $$ then $$ GCD(P_1,P_2)=\prod_{Q\in Irr(R)}Q^{\,\max(\nu_Q(P_1)\,,\,\nu_Q(P_2))} $$ If $R$ is a UFD [1], by the theory of content [2], so is $R[X]$. Now the algorithm for the GCD is clear.

1. Let $P_i,\ I=1,2$ be polynomials $R[X]$.
2. Compute $P_3$, the $GCD$ in $K[X]$ (where $K$ be the fraction field of $R$, here it is $\mathbb{Q}$) by Euclid's algorithm
3. With $c(P_i)$ as the content of $P_i$, $$ \mathcal{N}(P_3)=GCD(c(P_1),c(P_2))\times \Big(\frac{P_3}{c(P_3)}\Big)\in R[X] $$ is a GCD of $P_1,P_2$.

1. Unique factorization domain

2. Primitive part and content