Yun's algorithm and integers Does Yun's algorithm work with polynomials which have integer coefficients and are not necessary monic?
Wikipedia says "polynomials over a field of characteristic 0" but this is what confuses me. I would say yes because I could add many ones and never reach zero but I thought integers form (are?) a ring, not a field.
Put differently, are those divisions in Yun's algorithm always realizable with plain integers? Are those division always "exact"?
 A: Yes, it will work for $\mathbb Z[x]$ because the steps in the algorithm deal purely with

*

*GCDs, which exist in $\mathbb Z[x]$ because it is a unique factorization domain. Furthermore, elements have finite factorizations, so the algorithm can terminate.

*divisions which are guaranteed to work, because you are dividing by divisors

*differences between things in $\mathbb Z[x]$ and

*we have that the formal derivative of something in $\mathbb Z[x]$ is also in $\mathbb Z[x]$.

You can't get around needing characteristic $0$ though.  Suppose the characteristic was $2$, for example, and look at what happens to $f(x)=x^2+x$.  The condition on the characteristic keeps information from being blown away by the formal derivative.
A: Yes. It works with polynomials over the integers (which is expressed with "polynomials over a field of characteristic 0").
The divisions in the algorithm are polynomial long divisions resulting in other polynomials, in this sense they are exact.
By the same token, the GCDs in the algorithm are polynomial GCDs returning polynomials.
(The polynomial GCD raises a little technical problem because the polynomial GCD is only unique up to a unit (+1 or -1), but that doesn't seem to be your question.).
