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 = 155 + 34i, a = 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/a: a/a = (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. The remainder is: a = a - q*a = 20 + 48i We repeat the process, by computing a/a = 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 = 1 - 2i and the remainder is: a = a - q*a = 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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.