Tuesday, July 25, 2006

Cyclotomic Integers: Periods mod p

Today's blog continues the details that are used by Ernst Kummer in his theory of ideal numbers. He then uses ideal numbers in his proof for Fermat's Last Theorem for regular primes.

The contents of today's blog are taken from Harold M. Edwards Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.

In previous blogs, I have talked about cyclotomic integers and cyclotomic periods derived from cyclotomic integers. In today's blog, I will focus on a single, very important result. That for any prime p where p ≠ λ, there exists an integer f = exponent mod λ (see definition 2, here) and an integer e = (λ - 1)/f (see definition 3, here).

This means that for any prime p, there exist a set of e cyclotomic periods that each have a length of f elements (see here for review of the basic properties of cyclotomic periods).

Lemma 1: xp - x ≡ (x-1)(x-2)*...*(x-p) ≡ 0 (mod p)

Proof:

(1) Fermat's Little Theorem gives us:

xp-1 ≡ 1 (mod p)

So that:

p divides xp-1 - 1

So that:

x(xp-1 - 1) = xp - x ≡ 0 (mod p)

(2) We also know that:

(x -1)*(x-2)*...(x-p) ≡ 0 (mod p)

(a) There exists a r such that x ≡ r (mod p)

(b) We know that p divides x - r

(c) We also know that r is between 0 and p-1.

(d) if r is 0, then p divides x-p; otherwise, p divides x-r.

(3) Putting (#1) and (#2) together, we have:

xp - x ≡ (x-1)(x-2)*...*(x-p) ≡ 0 (mod p)

QED

Lemma 2: g(α) = g(αp) if and only if g(α) is a cyclotomic integer made up of periods of length f.

Proof:

(1) Let λ be an odd prime.

(2) Let α be a primitive root of unity such that αλ = 1.

(3) Let p be an odd prime distinct from λ

(4) Let τ be mapping such that τα = αp

(5) Let f be the least positive integer for which pf ≡ 1 (mod λ)

(6) We know that f divides λ -1 (see Lemma 1, here)

(7) Let e= (λ-1)/f

(8) Assume that g(α) is made up of periods of length f. [See here for review of cyclotomic periods]

(9) Then, σeg(α) = g(α) [See Lemma 4 here for details.]

(10) Then, there must exist an integer k such that:

τ = σk

Since the primitive root (see here for review if needed) can take all possible values mod λ [By definition σ = a mapping between α and αγ where γ is a primitive root, see here]

(11) Using step #10, we note that:

τf = σkf

Since τf ≡ 1 (mod λ), we know that σkf ≡ 1 (mod λ)

(12) Since the order of λ is λ -1 (see here), we know that kf must be divisible by λ - 1 (see Lemma 2 here) which means it is divisible by ef since ef=λ - 1.

So, ef divides kf means that e must divide k.

(13) So, from step #10 and step #12:

τ is a power of σe

(14) So, there exists k' such that ek' = k.

(15) From #14, we have:

τ = (σ1e)(σ2e)...(σk'e)

and therefore:

τg(α) =(σ1e)(σ2e)...(σk'e)g(α) = g(α)

(16) Assume that τg(α) = g(α)

(17) We know that there exists k such that:

τ = σk [Since σ is a mapping to γ which is a primitive root and the primitive root can take on all values modulo λ]

(18) Since g(α) repeats at τg(α), we know that g(α) consists of e periods of length f. [See Corollary 1.2 here]

(19) By definition, e divides (λ - 1) [See here for definition of periods]

(20) Thus, e is a common divisor of k and λ - 1.

(21) e is the greatest common divisor of k and λ - 1 since:

(a) Let d be an integer that divides both k, λ-1 so that:

k = qd
λ - 1 = df'

(b) Now,

τf' = σkf' = σqdf' = σ(λ - 1)q which is identity[from step #17, #21a, and since σλ-1 is the identity, see here]

(c) So that:

f' ≥ f [Since f is least value where pf ≡ 1 (mod λ)]
d ≤ e [Because d = (λ-1)/f' where f' ≥ f and e=(λ - 1)/f]

(22) Using Bezout's Identity, there exists a,b such that:

e = ak + b(λ - 1)

(23) Further,

σe = σakσb(λ-1) = [from step #22]

= σak = [Since σb(λ-1) is identity]

= τa [Since τ = σk from step #17]

(24) From this, we see that:

σeg(α) = τag(α) = g(α)

QED

Theorem 3: For any cyclotomic integer g(α) made up of periods of length f where f is the exponent mod λ for p, there exists an integer u such that g(α) ≡ u (mod p)

Proof:

(1) From Lemma 1 above, we have:

xp - x ≡ (x-1)(x-2)*...*(x-p) (mod p)

(2) Let x = g(α)

(3) Then:

g(α)p - g(α) ≡ [g(α) - 1][g(α) - 2]*...*[g(α) - p] (mod p)

(4) From a previous result (see Lemma 3 here), where g(α)p ≡ g(αp) (mod p), we have:

g(αp) - g(α) ≡ [g(α) - 1][g(α) - 2]*...*[g(α) - p] (mod p)

(5) Now, since g(α) is made up of periods of length f, we know that g(αp) = g(α) [See Lemma 2 above]

So that:

g(αp) - g(α) = 0 ≡ 0 (mod p)

(9) This gives us:

[g(α) - 1][g(α) - 2][g(α) - 3]*...*[g(α)-p] ≡ 0 (mod p)

(10) So at least one of these values must be divisible by p (otherwise, the product of each g(α) - u could not be 0.)

(11) So there exists an integer u such that p divides g(α) - u

Which means that:

g(α) ≡ u (mod p)

QED

Corollary 3.1: For each of the e cyclotomic periods ηi for a given odd prime p, there exists an integer ui such that ηi ≡ ui (mod p)

Proof:

(1) Each period ηi can be thought of as a cyclotomic integer made up of periods of length f:

g(α) = (0)η0 + ... + (1)ηi + ... + (0)ηe-1 = ηi

(2) From Theorem 3 above, we know that there exists an integer ui such that g(α) ≡ ui (mod p)

(3) So, we see that for each ηi, there exists ui such that:

ηi ≡ ui (mod p)

QED

Cyclotomic Integers: Unique Factorization Fails

Unique factorization fails for cyclotomic integers starting with λ = 23 where λ represent the primitive root of unity that a given cyclotomic integer is based on. For details on cyclotomic integers start here. This blog is part of the general proof that shows that Fermat's Last Theorem is true for regular primes.

The content is today's blog is based on Harold M. Edwards' Fermat's Last Theorem: A Genetic Introduction for Algebraic Number Theory. In today's blog, I take one result from Edwards. Edwards goes over a much more complete list of calculations taken from Ernst Kummer's original article.

Theorem 1: Not all cyclotomic integers are characterized by unique factorization

Proof:

(1) The method of this proof is to show that unique factorization fails for the number 47 when λ = 23.

NOTE: We only need to show one case of failure to show that unique factorization fails.

(2) Norm of (1 - α + α21) = 47*139.

NOTE: These calculations are taken directly from Edwards. If you see any mistake, please compare it to Edwards' book for the correction. Edwards takes his calculations from Kummer's original paper.

(a) Nf(α) = f(α)*f(α2)*...*f(αλ-1) [Nf(α) = Norm of f(α) See Definition 2, here]

(b) Let G(α) = f(α)f(α4)f(α-7)f(α-5)f(α3)f(α-11)f(α2)f(α8)f(α9)f(α-10)f(α6)

where α-x = α23-x

(c) Then Nf(α) = G(α)G(α-2)

since G(α-2) = f(α-2)f(α-8)f(α14)f(α10)f(α-6)f(α22)f(α-4)f(α-16)f(α-18)f(α20)f(α-12)

To be clear:

G(α) = f(α)f(α4)f(α16)f(α18)f(α3)f(α12)f(α2)f(α8)f(α9)f(α13)f(α6)

G(α-2) = f(α21)f(α15)f(α14)f(α10)f(α17)f(α22)f(α19)f(α7)f(α5)f(α20)f(α11)

(d) Let:

g(α) = f(α)f(α4)

h(α) = g(α)f(α-7)

(e) Then:

G(α) = h(α)h(α-5)h(α2)g(α-10)

since this equals:

[f(α)f(α4)f(α16)][f(α18)f(α3)f(α12)][f(α2)f(α8)f(α9)][f(α13)f(α6)]

(f) Now, we can do the following computations:

g(α) = f(α)f(α4) = (1 - α + α21)(1 - α4 + α15) =
= α21 - α16 + α15 + α13 + α5 - α4 - α2 - α + 1.

h(α) = g(α)f(α-7) =
= (α21 - α16 + α15 + α13 + α5 - α4 - α2 - α + 1)(1 - α16 + α10) =
= α20 + α19 + α17 -3α16 + α13 + α12 + α9 - α8 - α7 + α5 - α2 - α + 1.

h(α-5) = α15 + α20 + α7 - 3α12 + α4 + α9 + α - α6 - α11 + α21 - α13 - α18 + 1.

h(α2) = α17 + α15 + α11 - 3α9 + α3 + α + α18 - α16 - α14 + α10 - α4 - α2 + 1

g(α-10) = α20 - α + α11 + α8 + α19 - α6 - α3 - α13 + 1

(g) So, G(α) = -44 + 15θ0 - 13θ1

where θ0 = α + α4 + α-7 + ... + α6 and θ1 = -1 - θ0.

(h) Now, we can check it to find:

θ0θ1 = 11 + 5θ0 + 5θ1 = 6.

(i) Now, we are ready to put the calculation all together so that:

N(1 - α + α21) = G(α)G(α-2) =

= (-31 + 28θ0)(-31 + 28θ1) = 312 - 31*28(θ0 + θ1) + 6*282 = 961 + 868 + 4704 = 6533 = 47*139.


(3) Norm(47) = 47*47*....*47 = 4722.

(4) Norm(139) = 139*139*...*139 = 13922

(5) But, then (1 - α + α21) doesn't divide 47 and (1 - α + α21) doesn't divide 139 since (from Lemma 6, here), a cyclotomic only divides another cyclotomic integer if the norm of the first cyclotomic integer divides the norm of the second cyclotomic integer.

NOTE: In other words, 47*139 does not divide 13922 and likewise, 47*139 does not divide 4722.

(6) And this violates Euclid's Lemma since (1 - α + α21) does divide 47*139 by the equation in step #2 but it doesn't divide 47 and it doesn't divide 139.

NOTE: The equation proved in step #2 is:

N(1 - α + α21) = (1 - α + α21)*(1 - α2 + α21)*...*(1 - α21 + α21) = 47*139.

(7) And this means that unique factorization does not exist in this situation. [See here for details on the Fundamental Theorem of Arithmetic and its dependence on Euclid's Lemma]

QED

Kummer then developed his theory of ideal numbers in order to save unique factorization for cyclotomic integers.

Cyclotomic Integers: Ideal Numbers

Ernst Kummer wrote a very influential paper which demonstrated that unique factorization failed for certain cyclotomic integers including those based on α23=1. This paper invalidated Gabriel Lame's proposed proof for Fermat's Last Theorem. Harold M. Edwards goes into details on the methods that Kummer used and the nature of his discoveries. In a future blog, I will show how unique factorization fails for cyclotomic integers Z[α] where α23 = 1. [See here for details].

Kummer developed the theory of ideal numbers as an effort to save unique factorization for cyclotomic integers. In today's blog, I will go into detail on Kummer's theory of ideal numbers and show a proof that ideal numbers do, in fact, save unique factorization. The content in today's blog is taken from Harold M. Edwards book Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.

Definition 1: Z[α] where αλ = 1

This is the set of cyclotomic integers derived from the primitive root of unity based on an odd prime λ where a cyclotomic integer f(α) can be represented as follows:

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

where ai is a standard integer, λ is an odd prime, and α is the primitive root of unity based on λ.

I use α to represent the primitive root of unity and λ to represent an odd prime. I will represent a cyclotomic integer as a function that takes α as its parameter. For example, a(α), b(α), c(α), etc. are all cyclotomic integers. These conventions are also used by Edwards in his book and was used by Kummer in his original paper. If you need a review of cyclotomic integers and roots of unity, start here. See here for a proof that all cyclotomic integers can be represented in a form a0 + a1α + ... + aλ-1αλ-1.

Definition 2: Exponent mod λ

For a given prime p where p ≠ λ, if f is the exponent mod λ, then f is the lowest positive integer where pf ≡ 1 (mod λ).

As a convention, since the exponent mod λ is a standard integer, I will represent it as f.

Lemma 1: For any given prime p where p ≠ λ, the exponent mod λ divides λ - 1.

Proof:

(1) pλ-1 ≡ 1 (mod λ) from Fermat's Little Theorem (since p,λ are distinct primes)

(2) From a previous result (see Lemma 2 here), we know if f is the least positive integer, then it must divide λ-1.

QED

Definition 3: e = (λ - 1)/f

Since the exponent mod λ divides λ - 1, as a convention, I will refer to this result as e.

The integer e is very important in the construction of ideal numbers and gives us the useful equation ef = λ - 1.

Definition 4: ψ(η)p

This is a cyclotomic integer that is constructed in the following manner:

(1) Let f be the exponent mod λ for p and e = (λ - 1)/f.

(2) Consider the list of e*p cyclotomic integers that consist of the following form:

j - ηi where j = 1, 2, ..., p and i = 1, 2, ..., e

where ηi is a cyclotomic period associated with e. [See here for details on cyclotomic periods and how they can be derived from any factor of λ - 1]

(3) Now, remove from this list all values that are divisible by p.

We know that for all ηi there is an standard integer ui such that ηi ≡ ui (mod p) [See Corollary 3.1, here]

So ui which is in the list from 1, 2, ..., p means that ηi - ui gets removed.

NOTE: We know that there are e of these values so that at the end there are ep - e remaining values.

(4) Finally, define ψ(η)p = the product of all the remaining ep - e values such that:

ψ(η)p = (1 - η1)(2 - η1)*...*(p - ηe)

Assuming, of course, that 1 - η1, 2 - η1, p - ηe, etc. are not removed.

In review, there is a different ψ(η) for each prime p. I follow the convention from Edwards of putting η as a parameter to ψ since it is based on the cyclotomic periods.

I will also need to define a function σ.

Definition 5: σ

Let σ represent the transformation α → αγ where γ is the primitive root mod λ.

This transformation is a bit tricky since it is using the primitive root (see here for review of primitive roots) for its transformation. Being the primitive root, we know that γλ ≡ γ (mod λ) so that σλ = σ and σλ-1f(α) = f(α).

I spoke about this function in a previous blog (see here for details).

Example 1: Z[α] for λ = 3.

In this case, all cyclotomic integers f(α) have the following form:

f(α) = a0 + a1α + a2α2

In this case, the primitive root is 2 since 21 ≡ 2 (mod 3), 22 ≡ 1 (mod 3), and 23 ≡ 2 (mod 3).

We can then see that σf(α) = a0 + a1α2 + a2α4 = a0 + a1α2 + a2α

We can see that σ2f(α) = σ(a0 + a1α2 + a2α) = a0 + a1α + a2α2

Now, we are ready to talk about ideal numbers. It turns out that ideal numbers are a bit unusual in their make up. They may or may not exist as real cyclotomic integers. I will talk more about this strangeness later on. The interesting point is that even when they don't exist as cyclotomic integers, it is possible to define an "action" using them. For now, I start with one form of ideal numbers called prime divisors.

I won't offer a definition of prime divisors. Instead, I will offer a definition for the "action" of "division by a prime divisor."

Definition 6: Congruent mod a prime divisor of an integer p

Congruent mod a prime divisor means that a given cyclotomic integer g(α) satisfies 1 of 2 criteria:

Case 1: p ≠ λ

g(α) is said to be congruent h(α) mod a prime divisor of p ≠ λ if and only if

g(α)σi[ψ(η)p] ≡ h(α)σi[ψ(η)p] (mod p)

Case 2: p = λ

g(α) is said to be congruent h(α) mod a prime divisor of p = λ if and only if

g(α) ≡ h(α) (mod (α - 1))

Now, based on this definition, we can also define divisible by a prime divisor of a prime p.

Definition 7: Divisible by a prime divisor of an integer p.

A cyclotomic integer g(α) is said to be divisible by a prime divisor of an integer p if and only if g(α) is congruent to 0 mod the prime divisor of an integer p.


Observation:

Now, we can show that these definitions are useful by considering the following properties:

(1) Prime divisors when they exist as real cyclotomic integers satisfy the definitions above. [See Theorem, here]

(2) Divisibility by prime divisors saves Euclid's Lemma. In other words, if the product of two cyclotomic integers, say f(α)g(α) is divisible by a prime divisor, then either f(α) is divisible by the prime divisor or g(α) is divisible by the prime divisor. [See Lemma 2, below]

(3) All standard primes where p ≠ λ have e distinct prime divisors. [See here]

(4) λ has only 1 prime divisor which is the real cyclotomic integer α - 1. [See Lemma 3, here]

Definition 8: Divisible by a prime divisor of an integer p with multiplicity n

Divisible by a prime divisor with multiplicity n means that a given cyclotomic integer g(α) satisfies 1 of 2 criteria:

Case 1: p ≠ λ

g(α) is said to be divisible by a prime divisor of p ≠ λ if and only if

g(α)σi[ψ(η)p] ≡ 0 (mod pn) where i can be any positive integer.

Case 2: p ≡ λ

g(α) is said to be divisible by a prime divisor of λ if and only if

g(α) ≡ 0 (mod (α - 1)n)

Definition 9: Divisible by an ideal number

An ideal number is a set of powers of prime divisors. A cyclotomic integer is said to be divisible by an ideal number if it is divisible by all the prime divisors which make up the ideal number. A ideal number A is divisible by an ideal number B if and only if A contains all the same prime divisors as B with a multiplicity as great. There is a special ideal number I is consists of an empty set of prime divisors.

By convention, all ideal numbers are divisible by I.

Definition 10: Divisor

An ideal number A is said to be the divisor of a cyclotomic integer g(α) if it is divisible by all the prime divisors which divide g(α).

Now, finally, we can show that this construction of ideal numbers saves unique factorization.

If you would like to see a formal definition of prime divisor and ideal number, see here.

Lemma 2: Euclid's Lemma for Prime Divisors

if g(α)h(α) is divisible by a prime divisor P then g(α) is divisible by a prime divisor P or h(α) is divisible by a prime divisor P

Proof:

(1) g(α)h(α) is divisible by a prime divisor P means that g(α)h(α)ψ(η) ≡ 0 (mod p). [See Definition 7 above]

(2) This congruence relation is prime. That is, if g(α)h(α)ψ(η) ≡ 0 (mod p), then either g(α)ψ(η) ≡ 0 (mod p) or h(α)ψ(η) ≡ 0 (mod p) [See Lemma 2, here]

(3) But if g(α)ψ(η) ≡ 0 (mod p), then by definition 7 above, g(α) is divisible by a prime divisor P.

(4) On the other hand, if h(α)ψ(η) ≡ 0 (mod p), then by definition 7 above, h(α) is divisible by a prime divisor P.

(5) Either way we see that g(α)h(α) is divisible by a prime divisor P implies that either g(α) is divisible by a prime divisor P or h(α) is divisible by a prime divisor P.

QED

Theorem: Fundamental Theorem

A cyclotomic integer g(α) divides a cyclotomic integer h(α) if and only if every prime divisor which divides g(α) also divides h(α) with a multiplicity at least as great.

Proof:

Let λ be a given prime greater than 2 and let g(α), h(α) be nonzero cyclotomic integers built up from a λth root of unity α ≠ 1.

Then g(α) divides h(α) if and only if every prime divisor which divides g(α) also divides h(α) with multiplicity at least as great.

Proof:

(1) Let h(α) be divisible by g(α) such that h(α) = q(α)g(α)

(2) Certainly every prime divisor which divides g(α) also divides h(α) with multiplicity at least as great.

(3) Now g(α) divides h(α) if and only if Ng(α) = g(α)*g(α2)*...*g(αλ-1) divides h(α)*g(α2)*...*g(αλ-1)

(4) If every prime divisor which divides g(α) also divides h(α) with multiplicity at least as great then every prime divisor which divides Ng(α) also divides h(α)*g(α2)*...*g(αλ-1) with the multiplicity at least as great.

(5) Since Ng(α) is an integer, from this point on we can assume that g(α) is a rational integer and that h(α) = h(α)*g(α2)*...*g(αλ-1).

NOTE: The justification is that every cyclotomic integer can be made to depend on this equation where we show that every prime divisor that divides its norm necessarily divides the cyclotomic integer h(α)*g(α2)*...*g(αλ-1)

(6) Now, we will proceed to prove this theorem for 3 cases:

Case I: g(α) is a prime integer p ≠ λ

Case II: g(α) is a prime integer p = λ

Case III: g(α) is not a prime integer

(7) Assume g(α) is a prime integer p ≠ λ

(8) From a previous result (See Theorem 4, here), we know that if h(α) is divisible by each of the e prime divisors of p, then h(α) is divisible by p.

(9) Assume g(α) is a prime integer p = λ

(10) From a previous result (See Proposition 2, here), we know that if h(α) is divisible by (α - 1)λ - 1, then it is divisible by p = λ

(11) To prove case III, we will show that if the thereom is true for g1(α) and g2(α), then it is true for the product, g1(α)*g2(α)

(12) So, let us assume that all the prime divisors which divide g1(α)*g2(α) also divide h(α)

(13) Since all the prime divisors g1(α) divide h(α), then it follows that g1(α) divides h(α) and there exists h1(α) such that:

h(α) = g1(α)*h1(α)

(14) By assumption, every divisor of g2(α) divides h1(α).

(15) Since we are assuming that the theorem holds true for g2(α), then it follows that g2(α) divides h1(α) and there exists h2(α) such that:

h1(α) = g2(α)*h2(α)

(16) Therefore h(α) = g1(α)g2(α)h2(α) we have shown that h(α) is divisible by g1(α)g2(α)

QED

Corollary: Unique Factorization is "saved"

If two cyclotomic integers g(α) and h(α) are divisible by exactly the same prime divisors with exactly the same multiplicities, then they differ only by a unit multiple, g(α) = unit * h(α)

Proof:

(1) By the fundamental theorem above, g(α) divides h(α) and h(α) divides g(α)

(2) Therefore, h(α)/g(α) and g(α)/h(α) are cyclotomic integers.

(3) Since their product is 1, they must both be units. (See here for more details if needed)

QED

NOTE: On the Fundamental Theorem and Unique Factorization.

The use of the fundamental theorem "saves" the property of unique factorization for primes as shown by the corollary but there is a price to pay. With the integers, we can arbitrarily organize any combination of primes into numbers. For prime divisors, this is no longer the case. For example, for λ = 23, there is no cyclotomic integer which is divisible once by one prime divisor of 47 and not divisible by any other prime divisor.

I go into more detail about this in my blog on divisors.