Wednesday, June 15, 2005

Properties of Gaussian Integers

In my last blog, I spoke about relationship between Gaussian Integers and Fermat's Last Theorem. I went into some detail about norm function which provides a mapping from Gaussian Integers to standard integers. Anyone who is not familiar with Gaussian Integers or the norm function should start here. Anyone not familiar with the idea of unique factorization, should start here.

When we look at standard integers, officially called rational integers, we recognize that most of their properties are based on the Well Ordering Principle. This is the idea that for any given set of nonnegative integers, there is always one that is the smallest. If any one is interested in seeing the proofs related to the Well Ordering Principle and rational integers, you can check out here.

With Gaussian Integers, we are looking at a domain where the Well Ordering Principle does not apply. In the case of rational integers, it was clear that they can be thought to extend across a number line. Gaussian Integers, in contrast, extend across two number lines: a rational integer line and an i integer line.

For this reason, the previous proofs do not apply. We will need to come up with new proofs for the basic ideas. The basic idea of unique factorization is built from the following ideas:

(1) A Division Algorithm: What assumptions can we make about division? What assumptions can we make about quotients and remainders? See here for the algorithm with regard to rational integers. See here for the algorithm with regard to Gaussian Integers.

(2) Bezout's Identity: This is the idea that the greatest common denominator of any two integers can be represented as an equation based on two other integers. See here for the identity with regard to rational integers. See here for the proof of the identity with regard to Gaussian Integers.

(3) Euclid's Lemma: This is the idea that if a prime integer divides the product of two integers, then either it divides the first integer or it divides the second. See here for the proof of Euclid's Lemma regarding rational integers. See here for the proof with regard to Gaussian Integers.

Unique Factorization, it turns out, comes directly from Euclid's Lemma. As a convention, I will use Greek letters to represent Gaussian Integers and Latin letters to represent Rational Integers. So that: α = a + bi where α is a Gaussian Integer and a,b are rational integers.

There is one trick that we need to do in addition to using norms. We need to talk about the idea of associates.

Definition: Associates: Two numbers are associates if one is equal to the other multiplied by a unit.

The Gaussian Integers have four different units: i,-i,1,-1 (see Corollary 4.1, here). So, we can see that 4, -4, 4i, and -4i are all associates of each other. So, when we are talking about unique factorization of primes, we are considering prime associates to be the same prime. So, when we prove unique factorization, we are really proving a unique set of prime-associates.

Theorem: Gaussian Integers posess Unique Factorization.

(1) We know that all non-zero, non-units are either primes or composed of primes. [By the definition of primes]
(2) Let's assume that a given number is made of two different sets of primes.
(4) So α = β12*...*βr = γ12*...*γs
(5) Now each prime βi must necessarily match a prime in γj by Euclid's Generalized Lemma. [See here for the proof of Euclid's Generalized Lemma for Gaussian Integers]
(6) But we can make the same argument for all βi so there must be an equal prime or associate in the set of γj.
(7) But then, there cannot be any prime left over since if we divide all the βi, then we are left with a unit.
(8) So, we have proven that the set of primes is necessarily unique.

QED

Corollary: All Euclidean Integers posessess unique factorization.

(1) By definition, all Euclidean Integers are characterized by a Division Algorithm. [See here for review of Euclidean Integers]

(2) All Euclidean Integers are therefore also characterized by Euclid's Generalized Lemma. [See here for the proof.]

(3) With these two results, the same arguments above apply to all Euclidean Integers.

QED

10 comments:

Scouse Rob said...

"You will recall from my previous blog, that Gaussian Integers have 4 different units: i,-i,1,-1"

I don't recall this. Just that the Norm of a unit equals 1.

Rob

Larry Freeman said...

Hi Rob,

You are right. I've added a proof that these are the units and now link to this proof in the blog.

Thanks very much for the comment! :-)

Cheers,

-Larry

Kris said...

Hi, i've been using your blog to help me prove the unique factorisation of Gaussian integers, it's been helpful, thanks.

Just 1 thing I'm stuck on, and that is you don't prove that you can factorise all Gaussian integers into a product of Gaussian primes, you just state this and move on, and I think i should prove it, any help you can give?
Thanks,
Kris

Kris said...

Hi, i've been using your blog to help me prove the unique factorisation of Gaussian integers, it's been helpful, thanks.

Just 1 thing I'm stuck on, and that is you don't prove that you can factorise all Gaussian integers into a product of Gaussian primes, you just state this and move on, and I think i should prove it, any help you can give?
Thanks,
Kris

Larry Freeman said...

Hi Kris,

Thanks for your question. I want to make sure that I am clear on what issue you would like to see proved.

The following are implied in my proof:

(1) Gaussian Primes exist
(2) All numbers are either primes or consist of products of primes.
(3) All factorizations of a number into primes is unique.
(4) Gaussian Primes exist. Gaussian Nonprimes exist.

#1 is implied by the definition of primes, units, and associates.

For any Gaussian Integer, it is either decomposable into distinct products (not a unit or associate) or not.

#2 This is also clearly true based on #1. For any number, we can either decompose it into products of other distinct numbers or we cannot.

We are not proving that primes exist or that primes don't exist. Rather, I am showing that we have a criteria for determining whether any number is a prime or not.

#3 This is proven by the Theorem. The argument is that if a factorization exists, then it is unique.

#4 can be determined using Gaussian norms. The norm of a Gaussian prime will be a rational prime. The norm of a nonprime will be a nonprime.

The details on Gaussian Norms is fond here

Please let me know if you still have questions.

Cheers,

-Larry

Kris said...

Larry,
I am stuck on issue number 2.
When I proved the unique factorisation for integers, first I proved that all elements are a product of primes through strong induction (all numbers less than k are products of primes => k is a product of primes or prime)
Then I proved that the factorisation was unique.

For Gaussian integers, I see the step that says "We know that all non-zero, non-units are either primes or composed of primes. [By the definition of primes]" but I don't understand how this is so.

You say in your last post that "For any number, we can either decompose it into products of other distinct numbers or we cannot." But does this necessarily prove that all Gaussian integers are a product of Gaussian primes? To me it says that either a Gaussian integer is a prime or a product of other Gaussian integers.

Thanks, Kris

Kris said...
This comment has been removed by the author.
Kris said...

Just to clarify on the last point, saying that a Gaussian integer is a Gaussian prime or it is a product of other distinct numbers, I don't see how if it's a product of other distinct numbers, that these will necessarily lead to a prime factorisation

( for my proof of prime factorisations for integers, I first had to state that all integers up to n are either prime or a product of primes and then prove this inductively, and then state that the nth integer is either a prime or a product of smaller integers - these smaller integers must necessarily be a product of primes completing the proof )

Larry Freeman said...

Hi Kris,

(1) We know that Gaussian Integers exist from their definition.

They exist because integers exist and because we define a Gaussian integer as a a+bi where a,b are integers and i is the square root of -1.

(2) We know that all Gaussian Integers are either Primes, Units, Associates, or Composites of Primes.

This follows again logically by the definition of each of these terms in relation to Gaussian Integers.

For example, let U be the set of units, P be the set of primes and their associates, C be the set of numbers that are composed of primes.

It is clear that if G is the set of all Gaussian Integers G = U u P u C and these each of these sets are mutually exclusive. [This follows from their definitions]

(3) So, it follows directly from from (2), that all Gaussian Integers are either units, primes (and their associations), or products of primes.

That's all we need to prove for #2.

Mark said...

Thanks Larry,

I just found your blog; it's a wonderful resource. I'll be recommending it some of my more advanced students (middle school g/t).

In the last comment, though, shouldn't that be:

"if G is the set of all NON-ZERO Gaussian Integers G = U u P u C"?

Mark