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 α = β1*β2*...*βr = γ1*γ2*...*γ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.
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.