Antimatroid, The

thoughts on computer science, electronics, mathematics

Posts Tagged ‘Gaussian Integers

The ring of Gaussian Integers

leave a comment »

I recently started taking a foray into Complex Analysis as a means of filling in the gaps of my undergraduate mathematics knowledge. After reading about holomorphic functions, the Cauchy-Riemann equations and how to model ideal fluid flows I decided to take a break to digest it all. During this period I was reflecting on what I had done with Number Theory the previous summer and the question popped in my head: what is the complex equivalent of w \equiv v \pmod{z}? Or for that matter, are integer primes also primes in the complex domain (and vice versa)? And, are all complex z = \displaystyle\prod_{k = 0}^{\infty} p_{k}^{e_{k}} factorizations unique?

After looking around the internet for a while I came across a rather well written paper [pdf] by Assistant Professor Keith Conrad of the University of Connecticut that answered all of the questions brewing in my head along with the ones that weren’t. I’m going to surmise the basic ideas behind the solutions Conrad wrote about, if you have the free time it’s worthwhile to read the original text in its entirety.

If we consider the set of complex numbers of the form n + mi and restrict n, m \in \mathbb{Z} we have the set of the Gaussian Integers \mathbb{Z}[i]. If we take two values z, w \in \mathbb{Z}[i] we can say that z|w only if w = zu where u \in \mathbb{Z}[i]. Thus, \displaystyle\bar{z}w = \bar{z}zu \Rightarrow u = \frac{\bar{z}w}{\bar{z}z}. With this last step we’ve reduced the problem to satisfying two conditions: \displaystyle\bar{z}z|\Re{\bar{z}w} \wedge \bar{z}z|\Im{\bar{z}w}. For example let z = 1 + 2i, w = -5 + 10i \Rightarrow \bar{z}z = 5, \bar{z}w = 15 + 20i which satisfies the conditions 5|15 \wedge 5|20 \therefore z|w. For the congruence w \equiv v \pmod{z} with w,v,z \in \mathbb{Z}[i] to hold true, it must be the case that w = zu + v \Rightarrow z|(w - v).

Under \mathbb{Z} any integer m that is divisible by any integer other than a unit \pm 1 or unit multiple \pm m is said to be composite, otherwise m is said to be prime. The same definition holds in \mathbb{Z}[i] but our units are now \pm 1, \pm i and our unit multiples are now \pm z, \pm zi. As one might have guessed all primes in \mathbb{Z} are primes in \mathbb{Z}[i] however, the converse does not hold. For example 5 is prime but can be written as (1 + 2i)(1 - 2i) and is thus a composite number under \mathbb{Z}[i]. It is also useful to mention that if \bar{z}z \in \mathbb{P} then z is prime. By way of the Fundamental Theorem of Arithmetic, every composite integer can be written as the product of prime integers, this is also the case under \mathbb{Z}[i] and each factorization is unique.

The mechanics of finding the prime factorization of m \in \mathbb{Z}^{+} can be na├»vely done by trial division from n = 2 to \sqrt{m}. Once n|m reset n = 2 and m_{k} = m_{k - 1} / n and continue this procedure until m_{k} = 1. That is all well and fine for \mathbb{Z}^{+} but it isn’t immediately useful for doing the same under \mathbb{Z}[i].

For example, let’s consider z = -1395 - 12410i, since we are uncertain about how to factor z, lets think about how to factor \bar{z}z as we already know how to factor under \mathbb{Z} and see where that takes us. \bar{z}z = 155954125 = 5^{3} \cdot 61 \cdot 113 \cdot 181 We went from \mathbb{Z}[i] \to \mathbb{Z} so we’d hope that we could go the other way around by finding p = (n + mi)(n - mi) for each of the prime factors of \bar{z}z. In other words, we want to know p = n^{2} + m^{2} which will produce four Gaussian primes n \pm mi, m \pm ni. Thus, we find 5 = 1 + 2^{2}, 61 = 5^{2} + 6^{2}, 113 = 7^{2} + 8^{2}, 181 = 9^{2} + 10^{2}. Now, according to Conrad we should be able to pick any one of the four possible Guassian primes for each of the prime factors and multiply each Gaussian prime across, in doing so we get z = (2 + i)^{2} (2 - i) (6-5i) (8 - 7i) (10 - 9i). Now that’s pretty damn cool.

The general procedure for factoring a Gaussian Integer z into it’s prime components is to find the integer factorization of \bar{z}z and for each prime factor find p = n^{2} + m^{2}. Next, explore the Cartesian space formed by each factor’s four Gaussian primes until you come across a product coordinate that equals z and output said coordinate. As one can image this is a woefully poor algorithm for find the prime factorization of z. If anyone has ideas or knows of more efficient methods post them in the comments.

There is clearly much, much more to be said about Gaussian Integers, but this feels like a good stopping point. If you want to find out more about how some of the traditional Number Theory constructs are defined under \mathbb{Z}[i] you’ll want to read the entirety of Conrad’s paper or jump on Google and see what’s out there.

Written by lewellen

2008-08-10 at 8:05 pm

Posted in Number Theory

Tagged with