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.