2
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ @WillJagy This is ultimately what I'm trying to do: en.wikipedia.org/wiki/… When it says that the polynomial one starts with is assumed to be square-free, I assume that implies that for the general case one is supposed to do square-free factorization first. If Yun's algorithm doesn't apply since it requires GCD's, is there another algorithm that is recommended? $\endgroup$ Commented Jan 1, 2018 at 3:44
  • $\begingroup$ @WillJagy Also, what do you mean by a GCD not existing? That it isn't a well-defined concept? I don't see what part of the definition "the GCD of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials" doesn't apply to the integer case. The GCD could always be 1, of course, if the polynomials are coprime. $\endgroup$ Commented Jan 1, 2018 at 3:50
  • 1
    $\begingroup$ @WillJagy GCDs exist in any UFD. You may be confusing this with the existence of non-principal ideals. $\endgroup$
    – Sera Gunn
    Commented Jan 1, 2018 at 4:04
  • $\begingroup$ @TrevorGunn alright. Attributed to Gauss, if $R$ is a UFD, so is $R[x] \; .$ A feww pages earlier, in Rotman, a UFD does have the gcd of a finite set of elements. $\endgroup$
    – Will Jagy
    Commented Jan 1, 2018 at 4:06
  • $\begingroup$ @WillJagy I think Trevor is right. In a UFD every element $P$ factorizes as $$P=\lambda \prod_{R\in Irr}R^{\,\nu_R(P)}$$ where $\lambda$ is a unit and $Irr$ is a system of representatives of the irreducibles. Then $$GCD(P_1,P_2)=\prod_{R\in Irr}R^{\,max(\nu_R(P_1),\,\nu_R(P_2))}$$ $\endgroup$ Commented Jan 1, 2018 at 8:36

2 Answers 2

2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .