Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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

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
```
Associated Topics:
College Imaginary/Complex Numbers
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search