Re: A GCD question

On 7 Jul, 03:33, "sttscitr...@xxxxxxxxx" <sttscitr...@xxxxxxxxx>
wrote:
On 7 Jul, 02:34, Jeremy Boden <JeremyBo...@xxxxxxxxx> wrote:



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 sitehttp://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.

GCD(x + y, x^2 -x*y + y^2) =
GCD(x + y, (x+y)^2-3xy) =
GCD(x + y, -3xy)
So "numericlly", the only common divisors are -1,1,3,-3
So the GCD is 3. The only polynomial CDs are units

I did some of that earlier - but it doesn't follow that
GCD(x + y, -3xy) = 1 or 3 because A|(A^2 + 3B)does not imply that A|3B
Yet another example:-
x=4, y=2 then
GCD(x+y,x^2 -x*y + y^2) = GCD(6,16 -8 + 4) = GCD(6,12) = 6

However, if we impose the restriction that GCD(x,y) = 1
then x*y has no divisors (other than x or y)

Hence 3xy only has divisors of 3, x or y.
(x + y) is not divisible by x or y (trivial cases ignored),
Hence GCD(x + y, x^2 -x*y + y^2) = 1 or 3

Thanks for pointing out that
GCD(x + y, (x+y)^2-3xy) = GCD(x + y, -3xy) = 1 or 3

Shame about the GCD(polynomials) - it appears that this is "usually"
the unit.

Regards,
Jeremy

.

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: 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: High Precision Approximate GCD
    ... For given polynomial p and q, the degree of u; solve linear system ... Back to the GCD problem. ... Computing GCD is a two stage process. ... polynomials" that is now available at Math. ...
    (sci.math.symbolic)
  • Re: GCD of multivariate polynomials
    ... Christopher Creutzig wrote: ... I am looking for writing a program for computing the GCD of two ... >> multivariate polynomials in a fast and efficient way. ...
    (sci.math.symbolic)
Quantcast