34
$\begingroup$

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?

$\endgroup$
  • 11
    $\begingroup$ The G in GCD should not be understood as "greatest" with respect to the usual order of numbers but with respect to the divisibiity order. $\endgroup$ – Mariano Suárez-Álvarez Sep 6 '16 at 18:12
  • $\begingroup$ Also see math.stackexchange.com/a/495125/236182 $\endgroup$ – user236182 Sep 6 '16 at 23:11
  • $\begingroup$ You have to distinguish between ordinary language and technical language. For convenience, ordinary language is mixed with technical language, but you must guard against being misled by ordinary language. The worst (or, best) example of a disconnect between ordinary language and mathematical language concerns divisors of 0. According to the definition of a divisor, 23 is a divisor of 0, as is 37. Therefore, based on ordinary language, the real number system has divisors of 0, but according to mathematical language the real number system does NOT have divisors of 0. $\endgroup$ – Mike Jones Sep 11 '16 at 2:11
29
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "The existence of such principal ideas is exactly what it means to have unique factorization" What do you mean precisely? In general it is neither necessary nor sufficient (for the former, polynomials over a field in several variables for the latter the ring of [all] algebraic integers.) $\endgroup$ – quid Sep 6 '16 at 10:24
  • $\begingroup$ @quid No, you are stating that mixedmath's claim shows Bézout domain, which is insufficient to be PID hence UFD. Bit of unpacking to do! $\endgroup$ – Yakk Sep 6 '16 at 14:51
  • $\begingroup$ @Yakk yes, the second comment is on point: $\forall a, b \exists g: \langle a,b\rangle = \langle g \rangle$ means the domain is Bézout domain. This is neither necessary nor sufficient for being a UFD. It is sufficient if one imposes noetherian in addition, i.e. PID. $\endgroup$ – quid Sep 6 '16 at 15:57
  • 4
    $\begingroup$ @quid ah yes! Good catch --- indeed, I essentially only think about Noetherian rings, and I didn't think about it too hard. I will edit accordingly. $\endgroup$ – davidlowryduda Sep 6 '16 at 16:15
  • 1
    $\begingroup$ For "if $g$ has the following property" read "if $g$ is a divisor of $z$ and $w$ and has the following property". $\endgroup$ – bof Sep 8 '16 at 6:10
8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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$".

$\endgroup$
  • 3
    $\begingroup$ It might make sense to emphasis that for the natural number the 'new' definition gives exactly the same thing as the other one. Personally, I consider the first definition you gave a poor one, very close to "wrong." This is not to criticize the post; of course given the context it is relevant. Just to say that I never use and never teach the first definition, always the other one. $\endgroup$ – quid Sep 6 '16 at 10:14
  • $\begingroup$ But the "new" definition is not the same as the "old" definition anymore, even if they agree in some degree. So is it proper to still call this a GCD? Using the same name to mean different things is the straightest way into trouble :P $\endgroup$ – BarbaraKwarc Mar 20 '17 at 8:55
2
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ That's perhaps the most sensible norm function for the Gaussian integers, and certainly the most widely used, but it's not the only one, just as absolute value is not the only norm function for $\mathbb Z$. $\endgroup$ – Robert Soupe Sep 8 '16 at 2:11
2
$\begingroup$

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)$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ It does not depend on being Euclidean, but it is implied by it. Every UFD admits GCDs. Not every UFD is Euclidean, e.g., rings of polynomials over fields in several indeterminates. $\endgroup$ – quid Sep 6 '16 at 10:21
  • $\begingroup$ @quid You are correct; I will add an edit. $\endgroup$ – Fimpellizieri Sep 6 '16 at 17:42
  • $\begingroup$ A much easier example of non-Euclidean UFD for those who've studied $\mathbb{Z}[i]$ is $\mathcal O_{\mathbb Q(\sqrt{-19})}$. $\endgroup$ – Robert Soupe Sep 8 '16 at 1:17
  • $\begingroup$ @Robert, for that to be an easier example, the verification that it is not Euclidean should be easier. Is it? $\endgroup$ – Mariano Suárez-Álvarez Sep 8 '16 at 5:49
  • $\begingroup$ @Mariano Not if you haven't yet studied rings of polynomials at all. I don't see anything on this page that suggests either ankit or Fimpellizieri have studied such rings. Maybe I haven't either. $\endgroup$ – Robert Soupe Sep 8 '16 at 12:43
1
$\begingroup$

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 .

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.