Re: A GCD question

On Jul 6, 3:34 pm, Jeremy Boden <JeremyBo...@xxxxxxxxx> wrote:
I know it's easy to find the GCD of two integers using Euclid's
algorithm;
it's not much more difficult to find the GCD if two polynomials in a
similiar way.

But is it possible to do this for a multinomial?
I've been trying and failing to simplify
GCD(x + y, x^2 -x*y + y^2) - is this doomed to fail?

Regards,
Jeremy

Yes - it is possible.

Mathematica has a PolynomialGCD[x + y, x^2 -x*y + y^2] that returns 1
as the result.

Also see: http://icm.mcs.kent.edu/research/gcddemo.html

For a reference:

Three New Algorithms for Multivariate Polynomial GCD

T. Sasaki, M. Suzuki
Journal Title: Journal of Symbolic Computation
Date: 1992
Volume: 13
Issue: 4
p. 395 - 412

HTH - A

.

Relevant Pages

  • Re: euclidean algorithm over Q[i]
    ... Z, the Gaussian integers, may be what you remember seeing. ... written a pretty simplistic algorithm in java that carries out polynomial ... GCD, just using polynomial long division and the euclidean algorithm. ... GCD's of univariate polynomials over Q? ...
    (sci.math.symbolic)
  • Re: GCD of multivariate polynomials
    ... is necessary to simplify ratios of polynomials to simplest form. ... of GCD will come out faster. ... > What does work is a more generalized Euclidean gcd algorithm (divide ...
    (sci.math.symbolic)
  • Re: A GCD question
    ... it's not much more difficult to find the GCD if two polynomials in a ... I've been trying and failing to simplify ... Three New Algorithms for Multivariate Polynomial GCD ...
    (sci.math)
  • A GCD question
    ... I know it's easy to find the GCD of two integers using Euclid's ... it's not much more difficult to find the GCD if two polynomials in a ... I've been trying and failing to simplify ...
    (sci.math)
  • MACIS 2007 - CALL FOR PARTICIPATION
    ... Sciences (MACIS) is a new series of conferences where foundational research on theoretical and practical problems of mathematics for computing and information processing may be presented and discussed. ... Computing Roots of Polynomials using Bivariate Quadratic Clipping ... An algorithm for checking whether the toric ideal of an affine monomial curve is a complete intersection ...
    (comp.specification.z)