Saturday, May 13, 2006

Cyclotomic Integers: Factoring Fermat's Last Theorem

Today's blog continues the discussion of Kummer's proof of Fermat's Last Theorem for regular primes. If you would like to review the historical context for this proof, start here.

The major reason why cyclotomic integers are interesting in relation to Fermat's Last Theorem is because they enable us to factor Fermat's Last Theorem in the following way:

zn = xn + yn = (x + y)(x + αy)(x + α2y) .... (x + αn-1y)

Below I will show how I can derive this factoring using the Fundamental Theorem of Algebra.

Lemma 1: Let α be a primitive root of unity such that n is an odd prime and αn = 1, and let x,y,z be integers such that xn + yn = zn, then:

zn = xn + yn = (x + y)(x + αy)(x + α2y) .... (x + αn-1y)

Proof:

(1) We know that xn - 1 has n root from the Fundamental Theorem of Algebra.

(2) We also note that for all αi where 0 ≤ i ≤ n-1, we have i)n = 1.

NOTE: αn = 1 so it is really the same as α0.

(3) Based on #2, the Fundamental Theorem of Algebra gives us:

xn - 1 = (x - 1)*(x - α)*(x - α2)*...*(x - αn-1)

QED

Theorem 1: if n is odd, then zn = xn + yn = (x + y)(x + αy)(x + α2y) .... (x + αn-1y)

Proof:

(1) an - 1 = (a - 1)*(a - α)*(a - α2)*...*(a - αn-1) [From Lemma 1 above]

(2) Since a can be any value, let a = -x/y so that:

(-x/y)n - 1 = [(-x/y) - 1]*[(-x/y) - α]*...*[(-x/y) - αn-1] = -(x)n/yn - 1

(3) If we multiply (-y)n=-(yn) to both sides, we get:

xn + yn = (x + y)*(x + yα)*...*(x + αn-1y)

QED

Cyclotomic Integers: Division Algorithm

Today's blog continues the discussion of Kummer's proof of Fermat's Last Theorem for regular primes. If you would like to review the historical context for this proof, start here.

Today, I will continue reviewing the basic properties of cyclotomic integers. Today's content comes directly from Chapter 4 of Harold M. Edwards' Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.

Lemma 1: Criteria for division of a cyclotomic integer by a rational integer.

A cyclotomic integer is divisible by a rational integer if and only if all of its integer coefficients are congruent modulo the rational integer.

Proof:

(1) Let f(α) be a cyclotomic integer.

(2) f(α) = a0 + a1α + ... aλ-1αλ-1 [See Lemma 1 here for details]

(3) Let d be a rational integer.

(4) It is clear that if d divides f(α), then a0 ≡ a1 ≡ ... ≡ aλ-1 ≡ 0 (mod d).

(5) Assume a0 ≡ a1 ≡ ... ≡ aλ-1 (mod d).

(6) Then, using Corrolary 2.1 from here, we know that we can add aλ-1 to each of the coefficients to get:

f(α) = (a0 - aλ-1) + (a1 - aλ-1)α + ... + (aλ - 2 - aλ - 1λ-2 + (aλ-1 - aλ-1λ-1

(7) But then it is clear that d divides each of the coefficients so it divides f(α).

QED

Corollary 1.1: Division Algorithm for a cyclotomic integer f(α) by a rational integer d

if f(α) = a0 + a1α + ... + aλ-1αλ-1, the result is:

[(a0 - aλ-1)/d] + [(a1 - aλ-1)/d]α + ... + [(aλ-2 - aλ-1)/d]αλ-2

Proof:

(1) If d divides f(α), then a0 ≡ a1 ≡ ... ≡ aλ-1 (mod d) [From Lemma 1 above]

(2) By Corollary 2.1 here, we can add constant -c to each coefficient and still maintain the same value so that:

f(α) (a0 - aλ-1) + (a1 - aλ-1)α + ... + (aλ - 2 - aλ - 1λ-2 + (aλ-1 - aλ-1λ-1

(3) From this we know that d divides each coefficient and the result of this corrollary follows.

QED

Lemma 2: Division Algorithm for Cyclotomic Integers

A cyclotomic integer h(α) is divisible by another cyclotomic integer f(α) if and only if:

h(α)*f(α)-1 is divisible by the Nf(α)


(1) Let f(α),h(α) be cyclotomic integers.

(2) We can assume f(α) ≠ 0

(a) Assume f(α) = 0.

(b) Then, g(α) exists only if h(α) = 0 in which case g(α) can take any value.

(c) This resolves f(α) = 0 so we only need to address the case where f(α) ≠ 0.

(3) Assume f(α) * g(α) = h(α)

(4) Then, Nf(α)*g(α) = h(α) *f(α2)*f(α3)*...*f(αλ-1) = h(α)*f(α)-1

(5) We see that f(α) divides h(α) if and only if Nf(α) divides h(α)*f(α3)*...*f(αλ-1).

(6) But Nf(α) is a rational integer. [See Lemma 5 here]

(7) Let i(α) = h(α)*f(α)-1

(8) i(α) = b0 + b1α + ... + bλ-1αλ-1

(9) Using Lemma 1 above, we see that Nf(α) divides i(α) if and only if for any two coefficients bj ≡ bk (mod Nf(α))

(10) But from step #5, we have that f(α) divides h(α) if and only if after computing i(α) from step #8, we find that all coeffients of i(α) are congruent modulo Nf(α).

QED

Corollary 2.1: Method for determining result of division between two cyclotomic integers.

if f(α) = a0 + a1α + ... + aλ-1αλ-1 and:

h(α)f(α)-1 = b0 + b1α + ... + bλ-1αλ-1,

the result is:

[(b0 - bλ-1)/Nf(α)] + [(b1 - bλ-1)/Nf(α)]α + ... + [(bλ-2 - bλ-1)/Nf(α)]αλ-2

Proof:

(1) Let f(α), g(α), h(α) be cyclotomic integers with h(α) = f(α)g(α).

(2) Multiplying both sides by f(α)-1 gives us:

Nf(α)g(α) = h(α)f(α)-1

(3) Since Nf(α) is a rational integer, we can apply Corollary 1.1 above to get the desired result.

QED

Friday, May 12, 2006

Cyclotomic Integers: Units and Primes

Today's blog continues the discussion of Kummer's proof of Fermat's Last Theorem for regular primes. If you would like to review the historical context for this proof, start here.

Today, I will continue reviewing the basic properties of cyclotomic integers. Today's content comes directly from Chapter 4 of Harold M. Edwards' Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.

1. Unit

Definition 1: Cyclotomic Unit

A cyclotomic unit is a cyclotomic integer whose norm is 1.

So, if f(α) is a unit, then f(α)*f(α2)*...*f(αλ-1) = 1.

Definition 2: Cyclotomic Inverse

If f(α) is a unit, then f(α2)*..*f(αλ-1) is called the inverse and it represented as f(α)-1.

Lemma 1: if f(α)*g(α) = 1, then f(α) is a unit and g(α) = f(α2)*f(α3)*...*f(αλ-1).

Proof:

(1) Let f(α)*g(α) = 1.

(2) Nf(α)*Ng(α) = N(1) = 1 [See Lemma 6, here]

(3) So, Nf(α) = 1 [See Lemma 5, here]

(4) So, Nf(α) = f(α)*f(α2)*...*f(αλ-1) = 1 [Definition of Norm for Cyclotomic integers, here]

(5) So, f(α)*f(α2)*...*f(αλ-1) = f(α)*g(α) [Combining step #1 with step #4]

(6) Dividing both sides of step #5 by f(α) gives us the desired result.

QED

Lemma 2: A cyclotomic unit is a factor of any cyclotomic integer.

Proof:

(1) Let f(α) be a unit.

(2) Let h(α) be any cyclotomic integer.

(3) Let g(α) = h(α)*f(α)-1 [See definition 2 above]

(4) Then, h(α) = g(α)*f(α)

QED

2. Cyclotomic Primes

Definition 3: Irreducible

A cyclotomic integer h(α) is irreducible if for any factorization h(α)=f(α)*g(α), either f(α) or g(α) is a unit.

Definition 4: Cyclotomic Prime

A cyclotomic integer h(α) is prime if:

(a) if h(α) divides f(α)*g(α), then h(α) divides f(α) or g(α).

(b) there exists at least one cyclotomic integer f(α) that h(α) does not divide.

(c) if h(α) is not a factor of f(α) and it is not a factor of g(α), then it is not a factor of f(α)*g(α)

In rational integers, all irreducible nonunits are also primes. One of the question that needs to be addressed is whether this is still the case with cyclotomic integers. I will answer this question in a later blog.

3. More Properties of Units

Lemma 3: a unit * a unit = a unit

Proof:

(1) Let g(α),h(α) be units.

(2) By Lemma 6, here, if i(α)=g(α)*h(α), then Ni(α) = Ng(α)*Nh(α) = 1*1 = 1.

QED

Lemma 4: 1/unit = a unit

Proof:

(1) Let h(α) be a unit

(2) Nh(α) = h(α)*h(α2)*...*h(αλ-1) = 1. [See Definition 2, here for definition of norm for cyclotomic integers]

(3) From (#2), we can see that:

1/h(α) = h(α2)*...*h(αλ-1)

(4) Further, we can see that:

Norm(1/h(α)) = Nh(α2)*N(α3)*...*Nh(αλ-1) = 1*1*1*...*1 = 1 [See Lemma 6, here]

QED

Lemma 5: unit/unit = unit

Proof:

(1) Let h(α),g(α) be units.

(2) h(α)/g(α) = h(α)*(1/g(α))

(3) From Lemma 4 above, we know that (1/g(α)) is a unit.

(4) From Lemma 3 above, we know that a unit*unit = unit.

QED

Tuesday, May 09, 2006

Basic Properties of Cyclotomic Integers

Today's blog continues the discussion of Kummer's proof of Fermat's Last Theorem for regular primes. If you would like to review the historical context for this proof, start here.

Today, I will review the basic properties of cyclotomic integers. Today's content comes directly from Chapter 4 of Harold M. Edwards' Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.

1. Notation

For Kummer's notation, he used λ to represent the odd prime number and α to represent the root of unity so that we have:

Definition 1:
αλ = 1

2. Standard Form of Cyclotomic Integers

Lemma 1:
If a0, a1, ... aλ-1 are integers, then all cyclotomic integers for a given value of λ can be represented in the following form:

a0 + a1α + a2α2 + ... + aλ-1αλ-1

Proof:

(1) Let's assume that we have cyclotomic integer = a0 + a1α + a2α2 + ... + aλ-1αλ-1 + aλαλ

(2) By definition 1 above, αλ = 1

(3) So that we have:

(a0 + aλ) + a1α + a2α2 + ... + aλ-1αλ-1

(4) We can do the same thing for any power of αi where i ≥ λ

(5) So we can conclude that all values can be reduced to the form required.

QED

Lemma 2: For any given value of λ, 1 + α+α2 + ... + αλ-1 = 0

Proof:

(1) Since αλ = 1, we have:

1 + α+α2 + ... + αλ-1λ + α+α2 + ... + αλ-1 =

= α(αλ-1 + 1 + α+α2 + ... + αλ-2)

(2) Now, we know that α ≠ 0 since 0λ = 0 which contradicts with definition 1.

(3) We also know that α ≠ 1 since α is a λth root of unity [using Euler's Identity, see here], we know that α = e2iπ/λ

(4) So, therefore, 1 + α+α2 + ... + αλ-1 = 0

QED

Corollary 2.1: for any given integer c, a0 + a1α + a2α2 + ... + aλ-1αλ-1 = (a0 + c) + (a1 + c)α + (a2 + c)α2 + ... + (aλ-1 + c)αλ-1.

Proof:

(1) 1 + α + α2 + ... + αλ-1 = 0 [From Lemma 2 above]

(2) c + cα + cα2 + ... + cαλ-1 = c*0 = 0

(3) So that:

a0 + a1α + a2α2 + ... + aλ-1αλ-1 = a0 + a1α + a2α2 + ... + aλ-1αλ-1 + 0 =

= a0 + a1α + a2α2 + ... + aλ-1αλ-1 + c + cα + cα2 + ... + cαλ-1 =

= (a0 + c) + (a1 + c)α + (a2 + c)α2 + ... + (aλ-1 + c)αλ-1.

QED


3. Conjugates

Since each cyclotomic value can be represented as:

a0 + a1α + a2α2 + ... + aλ-1αλ-1

Kummer used the following shorthand to represent a cyclotomic integer:

f(α), g(α), φ(α), F(α), etc.

One important point that we find is that if f(α) = g(α), then f(α2) = g(α2) and so on up until λ - 1.

Lemma 2.5: Conjugates preserve relations between equations

That is, if f(α) = g(α), then f(αi) = g(αi) where i is a positive number less than λ, αi ≠ 1 and αλ = 1.

Proof:

(1) Let f(α) = a0 + a1α + ... + aλ-1αλ-1

(2) For any value f(αi) we see that:

f(αi) = a0 + a1αi + ... + aλ-1αi*(λ-1)

(3) In step #1, let j be the possible values ranging from 1 to λ -1. Combining this with step #2, we get:

f(αi) = ∑ ajαj*i

(4) To prove this lemma, we need to show each element j*i is congruent to a unique value of i modulo λ

In other words, we are trying to prove that each element of the f(αi) is distinct.

(5) This turns out to be the case from Lemma 1 here.

QED

For this reason, we say that f(α), f(α2), ...., and f(αλ-1) are conjugates of each other.

4. Norm

Definition 2: Norm of a cyclotomic integer f(α)

Nf(α) = f(α)*f(α2)*...*f(αλ-1)

I will now use this definition in the following proofs.

Lemma 3: Nf(α) = Nf(αi) for all values of i between 1 and λ-1.

Proof:

(1) Nf(αi) = f(αi)*f(α2*i)*...*f(αi(λ-1))

(2) Now, each value i, 2*i, 3*i, ... (λ-1)*i maps to a distinct value of 1,2,3,...,(λ-1) modulo λ (see Lemma 1 here)

(3) So in each case, i,2*i, etc. maps to a1*λ+1, a2*λ+2, etc.

(4) So we get Nf(αi) = f(αa0*λ+1)*f(αa1*λ+2)*...*f(αaλ-1*λ+λ-1) where ai is a nonnegative integer.

(5) Since αn*λ=1, we get:

Nf(αi) = f(α)*f(α2)*...*f(αλ-1)

QED

Lemma 4: αj = αλ-j

Proof:

(1) From roots of unity and Euler's Formula, we know that:

α = e(i2π/λ) = cos(2π/λ) + isin(2π/λ)

(2) We also know that the complex conjugate of a + bi is a - bi, so the complex conjugate for α is:

α = cos(2π/λ) - isin(2π/λ)

(3) Likewise, we know that the complex conjugate for αj is:

αj = cos(2jπ/λ) - isin(2jπ/λ)

(4) Using Euler's Formula, we see that:

e-2jπ/λ = cos(-2jπ/λ) + isin(-2jπ/λ)

(5) Since cos(-x) = cos(x) and sin(-x) = -sin(x) [see here], we can use (#4) to get:

e-2jπ/λ = cos(2jπ/λ) - isin(2jπ/λ)

which is from #3, the complex conjugate for αj

(6) Now, e-2jπ/λ = (e2π/λ)-j =

= α-j = α-jλ =

= αλ - j

QED

Corollary 4.1: f(αj) = f(αλ-j)

Proof:

(1) From Lemma 1, we have:

f(α) = a0 + a1α + a2α2 + ... + aλ-1αλ-1

(2) From this,

f(αj) = a0 + a1αj + a2α2*j + ... aλ-1αj*(λ-1)

(3) Now, from Lemma 4, we know that:

f(αj) = a0 + a1αλ-j + a2αλ - 2*j + ... aλ-1αλ - j*(λ-1)

(4) And, we know that:

f(αλ-j) = a0 + a1αλ-j + a2α(λ-j)*2 + ... aλ-1α(λ - j)*(λ - 1)

(5) Now,

n*λ - j*n ≡ λ - j*n (mod λ) [See here if you need a review of modular arithmetic]

(6) So that we see that step #3 and step #4 are equal so that:

f(αj) = f(αλ-j)

QED

Corollary 4.2: f(αj)*f(αλ-j) is a nonnegative real number

Proof:

(1) f(αj) * f(αλ-j) = f(αj)* f(αj) [From Corollary 4.1 above]

(2) So that:
f(αj) * f(αλ-j) = (a0 + a1αj + ... + aλ-1αj*(λ-1))(a0 + a1αj + ... + aλ-1αj*(λ-1)) =

= (a0)2 + (a1)2j*αj) + ... + (aλ-1)2j*(λ-1)*αj*(λ-1))

(3) Since each α*α is a nonnegative number, the conclusion follows.

QED

Lemma 5: For any cyclotomic integer f(α), its norm is a nonnegative rational integer.

Proof:

(1) Using Lemma 1 above, we know that:

Nf(α) = a0 + a1α + a2α2 + ... + aλ-1αλ-1

(2) By Lemma 3 above, we can substitute any conjugate αj and get the same norm so that:

Nf(αj) = Nf(α)

(3) But by changing to a conjugate, we keep the same coefficients but get the following:

Nf(αj) = a0 + a1αj + a2αj*2 + ... + aλ-1α(λ-1)*j

(4) Combining the two equations gets us:

a0 + a1αj + a2αj*2 + ... + aλ-1α(λ-1)*j = a0 + a1α + a2α2 + ... + aλ-1αλ-1

(5) Subtracting one from the other gives us:

a0 - a0 + (a1 - ajj + ... = 0

(6) Since we know that each of these j,2*j,...,(λ-1)*j matches up with a value 1,2,...,λ-1, we know that:

a1 = aj

(7) Further, since j can be any value from 2 thru λ-1, we can conclude the following:

a1 = a2 = a3 = ... = aλ-1

(8) So that:
Nf(α) = a0 + a1(α + α2 + ... + αλ-1)

(9) From Lemma 2, we know that:

1 + α+α2 + ... + αλ-1 = 0

so that:

α+α2 + ... + αλ-1 = -1

(10) So, we apply (#9) to (#8) to give us:

Nf(α) = a0 - a1

(11) We know that it is nonnegative since:

Nf(α) = [f(α1)*f(αλ-1)]*[f(α2)*f(αλ-2)]*...

(12) From Corollary 4.2 above, we know that multiplication of (λ-1)/2 pairs of nonnegative values will result in a nonnegative value.

QED

Lemma 6: f(α)g(α) = h(α) → Nf(α)*Ng(α) = Nh(α)

Proof:

(1) Let f(α)g(α) = h(α)

(2) By Definition 2 above:

Nf(α) = f(α)*f(α2)*...*f(αλ-1)

Ng(α) = g(α)*g(α2)*...*g(αλ-1)

Nh(α) = h(α)*h(α2)*...*h(αλ-1)

(3) Using step #1 gives us:

Nh(α) = f(α)*g(α)*f(α2)*g(α2)*...*f(αλ-1)*g(αλ-1) =

= f(α)*f(α2)*...*f(αλ-1) *g(α)*g(α2)*...*g(αλ-1) =

= Nf(α)*Ng(α)

QED

Sunday, May 07, 2006

Fermat's Last Theorem: Proof for regular primes

One of the highpoints of the 19th century mathematics is Kummer's proof of Fermat's Last Theorem for regular primes.

Kummer's theory of ideal numbers is one of the foundations of algebraic number theory. In future blogs, I will talk about some of the other very important proofs that came out at this time (impossibility of a general method for quintic equations, transcendence of π, and the fundamental theorem of algebra) and show how Dedekind reinterpreted many of these developments into the modern concepts of ideals, rings, groups, and fields.

Kummer's proof comes down to three major points.

(A) For certain primes (which Kummer called "regular primes"), cyclotomic integers can be said to have a form of unique factorization. [See here for discussion on ideal numbers and how they "save" unique factorization for cyclotomic integers]

(B) For a regular prime λ, there is no solution to xλ + yλ = zλ where x,y,z are pairwise relatively prime all prime to λ

(C) For a regular prime λ, there is no solution to xλ + yλ = zλ where x,y, z are pairwise relatively prime and where λ divides z.

For the full proof, go here.

References