Finding GCD of Complex Numbers with Euclidean Algorithm

Date: 10/11/2004 at 10:47:23
From: Viky
Subject: Euclidean algorithm

Hello Dr. Math,

I would like to calculate gcd(135-14i, 155+34i) via the Euclidean 
algorithm, but I don't know how to do that with complex numbers.

Kind regards,

Viky

Date: 10/12/2004 at 04:02:07
From: Doctor Jacques
Subject: Re: Euclidean algorithm

Hi Viky,

The complex numbers of the form x + yi, where x and y are integers, 
are called Gaussian integers.

You can compute the GCD of Gaussian integers in almost the same way as 
for ordinary integers.  The only difference is how to define the 
(Gaussian) integer quotient.

With ordinary integers, when we divide a by b, giving a = bq + r, we 
compute a/b and take q as the largest integer less than or equal to 
a/b (i.e., we "truncate" the rational quotient).

For Gaussian integers, you would divide a/b as complex numbers, giving 
x + yi (where x and y are not necesarily integers).  You will then 
take q as the Gaussian integer closest to x + yi, i.e., you round x 
and y to the nearest integer.  After q has been defined in this way, 
you define the remainder r as a - q*b, and repeat the process until 
you obtain a remainder of 0, which will happen when a quotient a/b has 
integer coefficients.

You should take as first number the one with the largest norm (the 
norm of x + yi is x^2 + y^2, the square of the absolute value--this is 
an integer if x and y are integers.  In this case, we have:

  N(135 - 14i) = 135^2 + 14^2 = 18421
  N(155 + 34i) = 155^2 + 34^2 = 25181

and we start with a[1] = 155 + 34i, a[2] = 135 - 14i.  (Note that 
there is no harm in starting in the opposite order, the first quotient
will be 0, and you will return to the previous case).

We compute the quotient a[1]/a[2]:

  a[1]/a[2] = (135 - 34i)/(144 + 14i) = 1.11 + 0.37i (approximately)

We round the real and imaginary parts to the nearest integers, giving 
the Gaussian integer quotient q[1] = 1.

The remainder is:

  a[3] = a[1] - q[1]*a[2] = 20 + 48i

We repeat the process, by computing a[2]/a[3] = 0.75 - 2.5i.  We round 
to the nearest integer--note that, for the imaginary part, we can 
round to either 2 or 3--the final result will be the same (up to a 
unit--see remark below).  Let us take:

  q[2] = 1 - 2i

and the remainder is:

  a[4] = a[2] - q[2]*a[3] = 19 - 22i

If you repeat the process, you should find a gcd equal to -5 - 12i 
(if I didn't make any mistakes).

Note, however, that there is some ambiguity in the definition of a GCD 
for Gaussian integers.  For normal integers, if d = gcd(a,b), then -d 
would be an acceptable gcd as well--both d and -d have the same sets 
of multiples and divisors.  We can choose to take the positive GCD as 
the "standard one", but this is only a convention.  The reason is 
that, in Z, 1 and -1 are "units", i.e., elements that have a 
multiplicative inverse, and these are the only such elements.

In Z[i], the Gaussian integers, there are actually 4 units: 1, -1, i, 
and -i.  This means that there are 4 equivalent (the correct term is 
"associate") GCD's for any pair of non-zero numbers: you can multiply 
the GCD by 1, -1, i, or -i.  In this case, the concept of "positive" 
is meaningless, and there is no way to define a "standard" GCD.  In 
the example, the four possible GCD's are:

  -5 - 12i, 5 + 12i, 12 - 5i, -12 + 5i

Does this help?  Write back if you'd like to talk about this some 
more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 10/14/2004 at 10:23:02
From: Viky
Subject: Thank you (Euclidean algorithm)

Thank you so much, Doctor Jacques!  Everything was clear, I understood
it all!

Greetings,

Viky