## Posts Tagged ‘**Gaussian Integers**’

## The ring of Gaussian Integers

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 ? Or for that matter, are integer primes also primes in the complex domain (and vice versa)? And, are all complex 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 and restrict we have the set of the Gaussian Integers . If we take two values we can say that only if where . Thus, . With this last step we’ve reduced the problem to satisfying two conditions: . For example let which satisfies the conditions . For the congruence with to hold true, it must be the case that .

Under any integer that is divisible by any integer other than a unit or unit multiple is said to be composite, otherwise is said to be prime. The same definition holds in but our units are now and our unit multiples are now . As one might have guessed all primes in are primes in however, the converse does not hold. For example is prime but can be written as and is thus a composite number under . It is also useful to mention that if then 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 and each factorization is unique.

The mechanics of finding the prime factorization of can be naïvely done by trial division from to . Once reset and and continue this procedure until . That is all well and fine for but it isn’t immediately useful for doing the same under .

For example, let’s consider , since we are uncertain about how to factor , lets think about how to factor as we already know how to factor under and see where that takes us. We went from so we’d hope that we could go the other way around by finding for each of the prime factors of . In other words, we want to know which will produce four Gaussian primes . Thus, we find , , , . 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 . Now that’s pretty damn cool.

The general procedure for factoring a Gaussian Integer into it’s prime components is to find the integer factorization of and for each prime factor find . Next, explore the Cartesian space formed by each factor’s four Gaussian primes until you come across a product coordinate that equals and output said coordinate. As one can image this is a woefully poor algorithm for find the prime factorization of . 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 you’ll want to read the entirety of Conrad’s paper or jump on Google and see what’s out there.