How can one talk about gcd in the context of complex numbers where order doesn't exist?

Question

I was reading this: GCD of gaussian integers but the thing that we are calculating, the GCD, doesn't make any sense in the complex number world since there is no ordering of numbers there. So, how can we define and calculate the GCD there?

Answer 1

There is a norm function on Gaussian integers. It is defined by $N(a+bi)= a^2+b^2$ (it is the square of the absolute value). On nonzero integers this function has the property that it takes values that are positive integers, and for given two elements $\alpha,\beta$ from the Gaussian integers, one can find two Gaussian integers $ q,r$ such that $\alpha = q\beta +r$ with either $N(r)=0$, or $N(r)<N(\beta)$. This makes the ring into what is called a Euclidean domain. So one has euclidean division with remainder possible.

This is good enough and gives the property you want out of an ordering.

(For polynomials it is the degree function)

Answer 2

Existence of a $\gcd$ does not depend on the ring itself being ordered, but rather on the existence of an Euclidean 'norm' function (for that ring) that allows one to perform the Euclidean algorithm to division. These rings are called Euclidean domains, and you can read more on them here, for instance.

The basic idea behind these Euclidean functions is that in a certain way they measure the 'simplicity' of the remainder of divisions, and most importantly that these remainders are always 'more simple' than what you started with, so that you eventually get down to a 'simplest element'.

EDIT: As pointed out by quid, what one actually needs is for our domain to have a unique factorization.

Answer 3

This is a great question, and perhaps deceptively deep.

One way to define the greatest common divisor of two Gaussian integers is as follows: given $z,w \in \mathbb{Z}[i]$, we call $g \neq 0$ a greatest common divisor of $z$ and $w$ if $g$ has the following property:

If $d \mid z$ and $d \mid w$, then necessarily $d \mid g$.

You might note that I mentioned that such a Gaussian integer is a greatest common divisor instead of the greatest common divisor --- this is because there isn't a single greatest common divisor. Unlike in the regular integers, there isn't an ordering (as you mention), so there is no good way to distinguish between different associates of the same integer.

For example, the greatest common divisors of $2$ and $4$ (in the Gaussian integers) are $2, 2i, -2i, -2$. Any one of these four could have been called a greatest common divisor.

This is a very general definition that works in many contexts, not just the Gaussian integers. [This works over $\mathbb{Z}$ too - you should try and prove it if you haven't].

Another way to define the greatest common divisor is to say $g$ is a greatest common divisor of $z,w \in \mathbb{Z}[i]$ if

1. $g \mid z$ and $g \mid w$, and
2. If $d \mid g$ and $d \mid w$, then $N(d) \leq N(g)$.

That is, a greatest common divisor is a common divisor of greatest norm.

For those with the mathematical maturity, another way of defining greatest common divisors relies on thinking of the integers as a ring. Then a greatest common divisor of $a$ and $b$ is a generator $g$ of the principal ideal containing $a,b$. That is, $\langle g \rangle = \langle a, b \rangle$. The existence of such principal ideals is closely related to what it means to have unique factorization. [This is also related to why being a Euclidean domain is stronger than being a unique factorization domain. Thanks to quid who noted an error in my answer in the comments below].

---

For a bit more about Gaussian integers and number theory, I note that I wrote up a few notes for my students of number theory once upon a time. Some others have found these notes useful.

Answer 4

We can partially order the Gaussian integers in terms of divisibility: $$a \ge b \iff \exists c \in \mathbb{Z}[i] \text{ such that } a = bc$$

in this case we say $b$ divides $a$, written $b|a$. So when we say that $d = \gcd(a,b)$ we mean that if $\tilde{d}|a$ and $\tilde{d}|b$ then $\tilde{d}|d$. This is the sense in which the gcd is "greatest". As for computing gcd's in the Gaussian integers the other (well written) answers above (and/or bellow) tell us that the Gaussian integers is a euclidean domain and so we can essentially use long division to nut it out.

Answer 5

The GCD for natural numbers is defined as "the largest common divisor". So $d = \gcd(a,b)$ if it is a common divisor and: $$ d' \mid a \textrm{ and } d' \mid b \implies d' \le d $$

Since we no longer have an ordering, we have to change our definition slightly: "the common divisor that is divisible by all other common divisors". Or, $$ d' \mid a \textrm{ and } d' \mid b \implies d' \mid d $$

This has a downside; there may now be multiple GCDs! For example, both $5$ and $-5$ are GCDs of $(10, 25)$. But it's easy to show that all GCDs must differ by a unit. So we have actually not lost too much.

This has the additional benefit of explaining why $\gcd(0, 0) = 0$. Everything divides $0$, so "greatest" common divisor doesn't exist. But there's only one number which all numbers divide, and that's zero. So $\gcd(0, 0) = 0$.

Furthermore, this definition of GCD becomes extremely natural in the context of ideals. Our new definition can be translated to "$d$ is a GCD of $a$ and $b$ $\iff$ the ideal generated by $d$ equals the ideal generated by $a$ and $b$".

Answer 6

I think that things could be explained more clearly just by following the steps of the founders of algebraic number theory, Dedekind et al. Let R be a domain and R* its group of units (= invertible elements in R). To define division between non zero elements of R, we must naturally speak « up to units », since units divide everybody. So, for x, d in R, we say that d ∣ x iff x is of the form x = udz, with z in R and u in R*, or equivalently, iff the principal ideal dR contains the principal ideal xR. A common divisor of x and y in R can obviously be defined in the same way : the principal ideal dR must contain the ideals xR and yR, or equivalently, must contain the ideal of R generated by x and y, say (x, y), which is also the smallest ideal (for inclusion) containing x and y.

The next natural step would be to define a GCD $\delta$ (up to units) of x and y by the condition $\delta$R = (x, y). If R is a PID, this works : there exists a $\delta$ in R such that (x, y) = $\delta$R (this is actually equivalent to Bézout’s theorem). If R is a UFD, this still works for another reason : (x, y) = $\delta$R, where $\delta$ (up to units) is the product of the irreducible elements which are common to the decompositions of x and y, taken with suitable powers. In your example, the Gaussian ring is an Euclidian domain (w.r.t. the norm, but it does not matter), hence is a PID. But the previous definition fails in general : if I and J are two ideals of A, the ideal generated by I and J is the ideal I + J consiting of the sums a + b, a in I, b in J, and that’s all. The way out, according to Dedekind (and following Kummer), is to define division for ideals, not for elements: I divides J iff I contains J ; then the GCD of I and J is the ideal I + J. Thus the UF property for ideals can be recovered in the so called Dedekind rings, in particular in the rings of integers of number fields, and a GCD ideal can be also naturally defined just as for elements in a genuine UFD .

Answer 7

Order does exist, just as it does in $\mathbb{Z}$. For example, what is $\gcd(-28, -98)$? We agree that $14$ is greater than $-14$ even though they are both the same distance away from $0$.

Now try $\gcd(-5 + i, -1 - 3i)$. There are four choices here, we choose to go with the one having positive real part and positive imaginary part.

As it turns out, divisibility provides a way to order numbers. Suppose we have three nonzero, non-unit numbers $a$, $b$, $c$. Then we expect there to be some kind of norm function $N(x)$ such that $N(a) < N(ab) < N(abc)$.