Re: gcd of two polynomials over Q[i]

Jeremy Watts <stevie4545@xxxxxxxxxxx> wrote:
this is carrying on from my previous post. i have attempted to find the gcd
of the following polynomials using the "wims" site,

http://wims.unice.fr/wims/wims.cgi?session=BO38B7C34A.3&lang=en&cmd=reply&mo
dule=tool%2Farithmetic%2Fbezout.en&x1=%286%2F5%29x%5E4%2B%28-39%2F5%2B622%2F
65i%29x%5E3%2B%281422%2F65-311%2F5i%29x%5E2%2B%28-72%2B5598%2F65i%29x%2B1296
%2F13&x2=%289%2F5%29x%5E3%2B%2857%2F5-24%2F13i%29x%5E2%2B%28-24-152%2F13i%29
x%2B320%2F13i&gcdlcm=yes&eucdiv=yes&euc1=1&euc2=2


Sorry, from this it is hard to see what your polynomials look like.


it seems to use the standard euclidean algorithm to accomplish this, but
from what i can see the gcd is :-

((8978642999775/15211817454289-11763279964575/15211817454289I)
x+(-156843732861000/197753626905757-119715239997000/197753626905757i))


but it claims that the gcd is 3/5x-8/13i (which is indeed the correct
answer)

How does it get from the answer with these horrifically high numbers to
3/5x - 8/13i ? My guess was that it divides throughout by the gcd of the
two complex numbers ie. the one being the coefficient of x, the other being
the constant term, hence my first post on complex gcd's.

is this correct? how does it finally arrive at 3/5x - 8/13i ?



Using Axiom and its factor command on your first polynomial I get:

8978642999775 11763279964575 40
(8) (-------------- - -------------- %i)(x - -- %i)
15211817454289 15211817454289 39

Using factor on the second polynomial I get:

3 40
(12) - (x - -- %i)
5 39

As you can see factor command here is has not much to do: since the
polynomials are of degree 1 all it has to do is to divide free term
by the coefficient of x.

Since gcd over fields is determined only up to constant both answers
are equivalent. How wims got the second ansver: it is probably an
artifact of algorithm used by wims.

--
Waldek Hebisch
hebisch@xxxxxxxxxxxxxxxx
.

Relevant Pages

  • gcd of two polynomials over Q[i]
    ... this is carrying on from my previous post. ... i have attempted to find the gcd ... of the following polynomials using the "wims" site, ...
    (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: 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)
Loading