Thursday, June 09, 2005

Unique Factorization

Carl Friedrich Gauss was the first mathematician to understand the importance of unique factorization in relation to algebraic integers. While unique factorization was a known property of integers since the time of Euclid, it is not true that it is necessarily a property of all algebraic integers.

Unique factorization is the idea that a given whole number consists of a unique set of primes. For every set of unique primes, there is one and only one number that can be built. For every number, there is one and only one unique set of primes.

Before Gauss, this idea was probably not interesting to mathematicians because it is so clearly true in the case of integers. On the other hand, when Leonhard Euler presented his proof for Fermat's Last Theorem n=3, he introduced a new set of integers in the form of a + b√-3. This was a brilliant proof and yet he made a mistake. He assumed that unique factorization automatically applied. It was Gauss's insight that this assumption requires proof.

Gauss took the idea of unique factorization very seriously when he proposed what are today called Gaussian Integers. Using i-notation, where i is the square root of -1, a Gaussian integer is defined by the set of all values that can be created by a + bi where a,b are integers. It is also represented by the form Z[i]. Using this notation, Euler's proof used integers of the form Z[√-3].

The interesting idea behind Gaussian Integers is that any theorem which is true of all Gaussian Integers is also true of all integers since integers are Gaussian Integers wheren b = 0.

But how does one reason with Gaussian Integers? On the surface, it doesn't look like they will be offer any insights beyond the standard integers. In fact, it seems, on the surface, that reasoning about them will be more difficult since they themselves are more complicated. Using standard integers, we know that 5 is a prime. But in the realm of Gaussian Integers, it is not a prime since
5 = (2 + i)(2 - i) = 4 + 1 = 5.

Gaussian Integers are interesting because they allow us to factor equations in interesting ways. For example, the equation x4 + y4 can now be factored into (x2 - y2i)(x2 + y2i). Without Gaussian Integers, there wouldn't be an easy factoring. This was really Euler's motivation for extending the integers since he was able to break x3 + y3 into a form such as:
(x + y)(x + ay)(x + by).

Coming up with proofs about Gaussian integers becomes interesting with the introduction of a special function called the norm. The norm is a mapping function that maps any Gaussian Integer to a standard integer. The norm is important because it enables to us to define Gaussian primes and because it then enables us to establish unique factorization for Gaussian Integers.

How does one find a mapping function that is guaranteed to convert any Gaussian Integer to a standard integer? The answer comes from the following mathematical equation:

(a + b)(a - b) = aa -ab +ab - bb = a2 - b2

In the case of i, this becomes:

(a + bi)(a - bi) = a2 - (b2)(-1) = a2 + b2.

The form a - bi is called the conjugate of the Gaussian Integer. Hardy and Wright (see reference below) define the norm as the product of a Gaussian Integer with its conjugate. For purposes of my discussion on Gaussian integers, I will use the Hardy and Wright definition (I should point out that this is not the standard definition of norm, see here; I will revisit this point at a later time). The important point behind the norm is that it is a mapping between the Gaussian integers and the rational integers that allows us to reason about the Gaussian integers (see here for an example of using the norm for Gaussian integers to establish a division algorithm for Gaussian integers.)

For example, the norm of 5i is (0 + 5i)(0 - 5i) = 25. Interestingly, the norm of -5i is also 25. This is important because it shows that the norm is not a one-to-one mapping. All Gaussian integers and their conjugates share the same norm.

In summary, I offer the following definitions for Gaussian Integers:

Definition 1: Conjugate of a Gaussian Integer

The conjugate of a Gaussian Integer a+bi is a-bi and likewise, the conjugate of a Gaussian Integer a-bi is a+bi.

Definition 2: Norm of a Gaussian Integer: N(α) = α * α

Following Hardy and Write (see article by Eric Weisstein for details), the norm of a Gaussian integer α is α multiplied by its conjugate α, that is, the norm N(α) = α * α.

Over the next set of blogs, I will show how norms allow us to establish unique factorization for Gaussian Integers. My next blog will cover some basic ideas about Gaussian Integer norms.



Jose Brox said...

Hi Larry:

You use a quite unconventional definition for the norm. I know that is sometimes used (like in Hardy&Wright), mostly referred to gaussian integers, but it's a bad choice because it doesn't fulfill all the properties traditionally asigned to a norm, and the complex norm has a square root: ||a+bi|| = Sqrt(a^2+b^2).

Regards. Jose Brox

Larry Freeman said...

Hi Jose,

Thank you very much for your comments.

I have added a note to the blog and also add a reference to the MathWorld article which discusses your point.

In the future, I will write a blog on this topic.

Thank you very much for noticing this and bringing it up! :-)


Tony Sudbery said...

Hi, Larry. Your blog gives the impression that Gauss was the first person to realise the need to prove unique factorisation for integers. You're only two thousand years out! Euclid saw the need for a proof and gave it as Proposition 14 of Book IX of his Elements.

Tony Sudbery

Larry Freeman said...

Hi Tony,

Thanks very much for your comment! You are absolutely correct that unique factorization as a concept has been well known since Euclid. The sentence as stated is incorrect.

My intention in the blog is to call out the importance of establishing unique factorization for the algebraic integers. This is what Gauss was the first to do and that is why we call Z[i], Gaussian Integers.

In light of your comments, I have updated my blog to make my main point more clear.



t0hierry said...

Hi Larry,

I'm reading your very informative post as a physicist. Is uniqueness of factorization similar in concept to that of orthonormal basis?

Larry Freeman said...

Hi T0hierry,

It is similar to orthonormal basis in the sense that an integer can be represented as a set of primes.

Unique factorization means that the integers can only be represented in one, unique way.

Not all integers have unique factorization. For example, the cyclotomic integers do not which resulted in a mistaken proof of Fermat's Last Theorem by Gabriel Lame.