Re: A GCD question

On 6 Jul, 23:48, amzoti <amz...@xxxxxxxxx> wrote:
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

Thanks for that - I see the web site http://icm.mcs.kent.edu/cgi-bin/icm.demo
uses Maxima (to obtain the same result).

If I substitute specific values for x & y that I can obtain different
results for the GCD.
E.g. let x=1, y=2
GCD(1+2, 1^2 - 1*2 + 2^2) = GCD(3,3) = 3
Clearly a GCD of a multinomial (or polynomial) will not necessarily
tell me anything about a GCD using specific numeric values.

Regards,

.

Relevant Pages

  • 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: 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: High Precision Approximate GCD
    ... gcd as a set of linear equations to be solved, ... values or when the polynomials are only _approximately_ equal to ... for the two polynomials, and using random leading coefficients as well, ... expanded forms of p and q had moved the roots around nearly as ...
    (sci.math.symbolic)
  • Re: euclidean algorithm over Q[i]
    ... apart from the final value for the gcd. ... Are you using the Euclidean algorithm to compute ... GCD's of univariate polynomials over Q? ... advantage to using 'pseudo division' to avoid large ...
    (sci.math.symbolic)
  • Re: A GCD question
    ... it's not much more difficult to find the GCD if two polynomials in a ... similiar way. ... Three New Algorithms for Multivariate Polynomial GCD ...
    (sci.math)