Tuesday, July 05, 2005

Quadratic Integers: Generalizing Gaussian Integers

Leonhard Euler proposed a proof for Fermat's Last Theorem: n = 3, using integers based on a+b-3. Carl Friedrich Gauss showed the need for a proof for uniqueness of factorization for a + b-1. Both of these integer extensions are examples of what we call today quadratic integers.

Quadratic integers are integers that are extended in the form of a + bα where α is an irrational value that is a solution to a quadratic equation. A quadratic equation is any equation that can be represented in the form x2 + bx + c = 0 where b,c are rational integers. The important point is that the coefficient for x2 needs to be 1 and the other coefficients need to be rational integers.

Applying basic algebra, we know that quadratic equations have the following solution:

Theorem: ax2 + bx + c = 0 → x = (-b ± b2 - 4ac)/2a.

(1) Subtracting c from both sides gives us:
ax2 + bx = -c

(2) Multiplying both sides by 4a gives us:
4a2x2 + 4abx = -4ac.

(3) Adding b2 to both sides, gives us:
4a2x2 + 4abx + b2 = b2 - 4ac.

(4) Now, since (2ax + b)*(2ax + b) = 4a2x2 + 4abx + b2, we get:
(2ax + b)2 = b2 - 4ac.

(5) Taking the square root of both sides, gives us:
2ax + b = ± b2 - 4ac

(6) Finally, subtracting b and then dividing both sides by 2a gives us our proof.

QED

From this formula, we see that Euler's integer is a solution to:
x2 + 3 = 0.

and Gaussian Integers are a solution to:
x2 + 1 = 0.

For purposes of notation, a set of quadratic integers is identified using a Z-notation. Z by itself represents the set of standard integers. Z[i] represents the set of Gaussian Integers. Z[-3] represents the set of Euler's integers.

Now, when it comes to integers of the form Z[d] where d ≡ 1 (mod 4), it turns out that an integer is of the form: (a + bd)/2 where a,b are both odd or both even.

To understand the mathematics behind this result, let's start out with a very simple lemma:

Lemma: a2 ≡ 1 or 0 (mod 4).

(1) We know that a ≡ 0, 1, 2, or 3 (mod 4).

(2) Now here's what we get for each of these values in the case of a2

(a) 02 ≡ 0 * 0 ≡ 0 (mod 4).
(b) 12 ≡ 1 * 1 ≡ 1 (mod 4).
(c) 22 ≡ 2 * 2 ≡ 0 (mod 4).
(d) 32 ≡ 3 * 3 ≡ 1 (mod 4).

QED

Here is the lemma that establishes this:

Lemma: for a set of quadratic integers Z[d] , if d ≡ 1 (mod 4), then the form of this quadratic integer is (a + bd)/2 where both a,b are even or both a,b are odd, otherwise, it is a + bd

(1) The goal here is to prove that (a + b√d)/2 is an integer, that is, it satisfies an equation of the form x2 + bx + c = 0.

(2) Now let's assume that we have a value α which is equal to (e + f√d)/2 where e,f are rational integers and d ≡ 1 (mod 4).

(3) Let x = (e + f√d)/2

(4) Then,
2x - e = f√d

(5) And squaring each side gives us:
4x2 - 4ex + e2 = f2d

(6) Which amounts to:
4x2 - 4ex + e2 - f2d = 0

(7) Now if we divide both sides by 4, we get:
x2 - ex + (1/4)[e2 - f2d] = 0

(8) Now, if both e,f are odd, then: [from the lemma above]
e2 - f2d ≡ 1 - 1*1 ≡ 0 (mod 4).

(9) Now, if both e,f are even, then: [from the lemma above]
e2 - f2d ≡ 0 - 0 * 1 ≡ 0 (mod 4).

(10) This value then meets our definition of quadratic integer.

QED

Corollary: if d ≡ 1 (mod 4), a number is an integer if it can be written as a + b[(1 + √d)/2], where a,b are rational integers.

(1) a + b(1 + √d)/2 = [(2a + b) + b√d]/2

If b is odd, then (2a + b) is odd. If b is even, then (2a + b) is even. In both cases (2a + b),b are both even or both odd.

(2) If a,b are both even or both odd.

(a + b√d)/2 = (a - b)/2 + b(1 + √d)/2

QED

The result of this is that in the case of d=-3, the set of integers is Z[(-1+√-3)/2] because we are dealing with integers of the form (a + b√-3)/2. I will go into more detail on this when I revisit a proof for n=3 based on Eisenstein integers.

The other interesting point about quadratic integers is that it turns out that not all of them are characterized by unique factorization and most of them are not characterized by a division algorithm.

I will go into more detail about this in my next blog.

The content of this blog is based in a large part on Harold M. Stark's An Introduction to Number Theory.