Re: euclidean algorithm over Q[i]


"Chip Eastham" <hardmath@xxxxxxxxx> wrote in message
news:1166245043.467094.262880@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

G. A. Edgar wrote:
In article <62tgh.6569$Dr3.1078@xxxxxxxxxxxxxxxxxxxx>, Jeremy Watts
<stevie4545@xxxxxxxxxxx> wrote:

how does the euclidean algorithm proceed for numbers in Q[i] ? my
knowledge
of abstract algebra's basic to say the least so i hope i am using the
correct term. i mean for complex numbers with rational real & complex
parts
ie. of form a/b + c/d i a,b,c,d in Z

i'm sure i have seen this somewhere but cant find reference to it
anywhere.

thanks



Q[i] is a field, so greatest common divisors are easy.
Any nonzero element divides any other nonzero element.

Z[i], the Gaussian integers, may be what you remember seeing.

--
G. A. Edgar
http://www.math.ohio-state.edu/~edgar/

And if the OP is interested in the Gaussian integers Z[i],
it is helpful to bear in mind that a Euclidean domain is
possessed of a norm. The "remainder" term is to have
norm less than the divisor in each application of the
division algorithm. Of course Z[i] is not an ordered ring,
so its important to pick the remainder to have minimum
norm as its defining characteristic.

The norm of z = a + bi is a^2 + b^2 in Z[i].

More discussion here:

yes of course, thank you both. the reason i'm asking this is because i've
written a pretty simplistic algorithm in java that carries out polynomial
GCD, just using polynomial long division and the euclidean algorithm.

i've been comparing the output with what 'wims' gives
http://wims.unice.fr/wims/wims.cgi?session=XKF67EF2A7.1&+lang=en&+module=too
l%2Farithmetic%2Fbezout.en

and they agree, apart from the final value for the gcd. which i assume
'wims' is getting somehow by avoiding intermediate 'coefficient swell'. i
have read that if you use 'pseudo division' rather than standard long
division you can get around this problem when working in the rationals


http://en.wikipedia.org/wiki/Gaussian_integer


regards, chip



.

Relevant Pages

  • Re: euclidean algorithm over Q[i]
    ... correct term. ... Z, the Gaussian integers, may be what you remember seeing. ... possessed of a norm. ... The "remainder" term is to have ...
    (sci.math.symbolic)
  • Re: Oh No
    ... I'm not so sure about Edgar. ... hold his pee long enough to box a round. ... In that case he's a slight underdog. ... SAM: "Whatcha up to Norm?" ...
    (rec.sport.boxing)
  • Re: getting freqz from fft (complex numbers)
    ... > It should be easy to remember the correct term because an L0 norm ... The L2 norm was the intersting one, ... > That won't work, Rune. ... Thanks, Andor, for the correction. ...
    (comp.dsp)
  • Re: Rest areas WI 29 East? (was Re: Best Cross Wisconsin route?)
    ... Norm wrote: ... Interested if anyone has any recent input on best route given construction areas. ... have to use gas stations/truck stops, the ones that I like most are at Cadott, Edgar, Abbotsford/Colby and US 45 south just east of Wittenburg. ...
    (misc.transport.road)
  • Re: getting freqz from fft (complex numbers)
    ... Rune Allnor wrote: ... > * This is the L0 or L1 norm of the spectrum, ... It should be easy to remember the correct term because an L0 norm ...
    (comp.dsp)