Thursday, November 03, 2005

Dirichlet Integers

Today's blog continues the proof for Fermat's Last Theorem: n = 5. If you are interested in the history behind the proof, start here. If you are just interested in the mathematical details behind the proof, start here.

Today's blog continues on the problem of factoring a2 - 5b2 using quadratic integers of the form Z[(1 + √5)/2]. For those interested in understanding why we are not using Z[√5], please see here.

For purposes of this blog, when I say Dirichlet integers, I mean integers of the form:

Z[(1 + √
5)/2]

That is, integers of the form a + b(1 + √5)/2 where a,b are rational integers.

The basic idea behind the use of quadratic integers in a proof is the following:

(i) Quadratic integers are easier to factor than rational integers.

For example, using Z[(1 + √5)/2] we can factor a2 - 5b2 into (a - b5)(a + b5).

(ii) As long as a quadratic integer has unique factorization, it is possible to use quadratic integers to prove existence lemmas.

In the case of Fermat's Last Theorem: n=5, we will use Z[(1 + √5)/2] to prove:

If there exist two integers a,b such that:

(a) gcd(a,b)=1
(b) a,b have different parities (one is odd, one is even)
(c) 5 doesn't divide a
(d) 5 divides b
(e) (a2 - 5b2) is a fifth power.

Then there exists two integers c,d such that:

(i) a = c(c4 + 50c2d2 + 125d4)
(ii) b = 5d(c4 + 10c2d2 + 5d4)
(iii) gcd(c,d)=1
(iv) c,d have different parities
(v) 5 doesn't divide c
(vi) c,d are nonzero

Let's review the basics of Z[(1 + √5)/2]:

Definition

From a previous blog, we know that Z[(1 + √5)/2] is defined as:

a + b(1+√5)/2 [Since 5 ≡ 1 (mod 4), see here]

We also note that Dirichlet integers are charaterized by unique factorization. [See here]

Unique Factorization means that when we are reasoning about Dirichlet Integers, we can make use of the Division Algorithm, Euclid's Lemma, the Fundamental Theorem of Arithmetic, and Relatively Prime Divisors of N-Powers.

Norm Function

The norm is a mapping between Dirichlet integers and rational integers. This function is very useful for identifying units, primes, and in general, reasoning about Dirichlet integers. For review of norms and conjugates, please see here.

A norm for a quadratic integer is equal to the quadratic integer multiplied by its conjugate. So, the first step in figuring out the norm is to figure out the conjugate for a given Dirichlet integer.

Let's start with a Dirichlet integer based on integers a,b:

a + b(1+√5)/2

Now, this value is equivalent to:

[(2a + b) + b5]/2

So, the conjugate would be:

[(2a + b) - b5]/2

To simplify, we can set a' = (2a + b), b' = b. We note that a',b' will always have the same parity. In other words, they will both be odd or they both will be even.

Using a',b', the norm is:

Norm = (a' + b'5)/2*(a' - b'5)/2 = (a'2 - 5b'2)/4

Putting back in (2a+b) for a' and b for b', gives us:

Norm = (a'2 - 5b'2)/4 = [(2a+b)2 - 5(b)2]/4 =
(4a2 + 4ab + b2 - 5b2)/4 =
(4a2 + 4ab - b2)/4 =
a2 + ab - b2

Unit

A unit is any quadratic integer that divides 1. Units are needed in order to establish unique factorization with quadratic integers. You can review the ideas behind units and associates by starting here.

From a previous result, we know that a unit is also any quadratic integers whose norm is ± 1.

This means that we can determine the units for Dirichlet integers by solving the following equation:

(a'2 - 5b'2)/4 = 1

Which is the same as this:

a'2 - 5b'2 = 4

This is a difficult problem. To find the solution, I will now take a short detour to talk about Pell's Equation (another difficult problem posed by Pierre de Fermat). I will then use the solution to Pell's Equation to identify the units for Dirichlet integers.

Of course, we can simplify the problem by considering a'2 - 5b'2 = -4 which is clearly a=1, b =1.

It turns out that all Dirichlet units have the same form:

±[(1 + √5)/2]±n

Lemma 2: All Dirichlet units have the following form: ±[(1 + √5)/2]±n

(1) We know that (1 + √5)/2 is a unit since:

Norm( (1 + √5)/2 ) = [(1 + √5)/2][(1 - √5)/2] = (1 - 5)/4 = -4/4 = -1

Any value that has a norm = ±1 is a unit. [See here for proof]

(2) Assume that there existed a unit α that does not have the above form.

(3) Let ω = (1 + √5)/2

(4) So, we know that there exists some integer n such that:

α is greater than ωn and is less than ωn+1

(5) We know that ωn is a unit and ωn+1 is a unit since Norm(xn) = Norm(x)*Norm(x)*...*Norm(x) = (± 1)(± 1)*...*(± 1)

(6) Since a unit by definition divides 1, we know that ω-(n) is a unit since ωn is a unit.

(7) Likewise, we know that any unit divides any other unit, so we can divide all values by ωn which gives us:
1 is less than α which is less than ω

(8) But there is no such unit that is between 1 and ω

(a) Let's assume that there is was such a unit β

(b) So, there exists two rational integers: x,y such that β = (x + y5)/2 that is greater than 1 and less than ω

(c) And (x + y5) is greater than 2 and less than 2*ω which is less than 4.

(d) Now, since β is a unit, we know that Norm(β) = ± 1 = [(x + y5)/2][(x - y5)/2]

(e) This means that x = 1 or x = 2 since:

Case I: [(x + y5)/2][(x - y5)/2] = 1

Since (x + y5)/2 is greater than 1, then (x - y5)/2 is greater than 0 and less than 1.

So, x - y5 is greater than 0 and less than 2.

So (x + y5 + x - y5) is greater than 2 and less than 6.

So 2x is greater than 2 and less than 6

So x = 2.

Case II: [(x + y5)/2][(x - y5)/2] = -1

Since (x + y5)/2 is greater than 1, then (x - y5)/2 is greater than -1 and less than 0.

So, x - y5 is greater than -2 and less than 0.

So (x + y5 + x - y5) is greater than 0 and less than 4.

So 2x is greater than 0 and less than 4

So x = 1.

(f) But x ≠ 1 since:

(1 + y5)/2 is greater than 1 so y must be greater than 0 but then (1 + y5)/2 cannot be less than (1 + √5)/2

(g) And x ≠ 2 since:

(2 + y5)/2 is greater than 1 so y must be greater than 0.
(2 + y5)/2 is less than (1 + √5)/2, so y must be less than 1.

But there is no integer between 0 and 1 so we have reached a contradiction.

QED

Primes

Lemma 3: √5 is also a prime in Z[(1 + √5)/2]

(1) exists since = (0 + 25)/2

(2) is prime since Norm(5) = -5 [See Lemma 5 here]

QED

Lemma 4: 2 is a prime in Z[(1 + √5)/2]

See here for proof.

1 comment:

Scouse Rob said...

In the penultimate line of the Norm Function:

(4a^2 + 4ab - b^2)/4

should be:

(4a^2 + 4ab - 4b^2)/4