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: x^p - x ≡ (x-1)(x-2)*...*(x-p) ≡ 0 (mod p)

Proof:

(1) Fermat's Little Theorem gives us:

x^p-1 ≡ 1 (mod p)

So that:

p divides x^p-1 - 1

So that:

x(x^p-1 - 1) = x^p - 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:

x^p - 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 p^f ≡ 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:

τ = (σ₁^e)(σ₂^e)...(σ_k'^e)

and therefore:

τg(α) =(σ₁^e)(σ₂^e)...(σ_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 p^f ≡ 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:

x^p - 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 u_i such that η_i ≡ u_i (mod p)

Proof:

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

g(α) = (0)η₀ + ... + (1)η_i + ... + (0)η_e-1 = η_i

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

(3) So, we see that for each η_i, there exists u_i such that:

η_i ≡ u_i (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 - α + α²¹) = 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(α²)*...*f(α^λ-1) [Nf(α) = Norm of f(α) See Definition 2, here]

(b) Let G(α) = f(α)f(α⁴)f(α^-7)f(α^-5)f(α³)f(α^-11)f(α²)f(α⁸)f(α⁹)f(α^-10)f(α⁶)

where α^-x = α^23-x

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

since G(α^-2) = f(α^-2)f(α^-8)f(α¹⁴)f(α¹⁰)f(α^-6)f(α²²)f(α^-4)f(α^-16)f(α^-18)f(α²⁰)f(α^-12)

To be clear:

G(α) = f(α)f(α⁴)f(α¹⁶)f(α¹⁸)f(α³)f(α¹²)f(α²)f(α⁸)f(α⁹)f(α¹³)f(α⁶)

G(α^-2) = f(α²¹)f(α¹⁵)f(α¹⁴)f(α¹⁰)f(α¹⁷)f(α²²)f(α¹⁹)f(α⁷)f(α⁵)f(α²⁰)f(α¹¹)

(d) Let:

g(α) = f(α)f(α⁴)

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

(e) Then:

G(α) = h(α)h(α^-5)h(α²)g(α^-10)

since this equals:

[f(α)f(α⁴)f(α¹⁶)][f(α¹⁸)f(α³)f(α¹²)][f(α²)f(α⁸)f(α⁹)][f(α¹³)f(α⁶)]

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

g(α) = f(α)f(α⁴) = (1 - α + α²¹)(1 - α⁴ + α¹⁵) =
= α²¹ - α¹⁶ + α¹⁵ + α¹³ + α⁵ - α⁴ - α² - α + 1.

h(α) = g(α)f(α^-7) =
= (α²¹ - α¹⁶ + α¹⁵ + α¹³ + α⁵ - α⁴ - α² - α + 1)(1 - α¹⁶ + α¹⁰) =
= α²⁰ + α¹⁹ + α¹⁷ -3α¹⁶ + α¹³ + α¹² + α⁹ - α⁸ - α⁷ + α⁵ - α² - α + 1.

h(α^-5) = α¹⁵ + α²⁰ + α⁷ - 3α¹² + α⁴ + α⁹ + α - α⁶ - α¹¹ + α²¹ - α¹³ - α¹⁸ + 1.

h(α²) = α¹⁷ + α¹⁵ + α¹¹ - 3α⁹ + α³ + α + α¹⁸ - α¹⁶ - α¹⁴ + α¹⁰ - α⁴ - α² + 1

g(α^-10) = α²⁰ - α + α¹¹ + α⁸ + α¹⁹ - α⁶ - α³ - α¹³ + 1

(g) So, G(α) = -44 + 15θ₀ - 13θ₁

where θ₀ = α + α⁴ + α^-7 + ... + α⁶ and θ₁ = -1 - θ₀.

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

θ₀θ₁ = 11 + 5θ₀ + 5θ₁ = 6.

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

N(1 - α + α²¹) = G(α)G(α^-2) =

= (-31 + 28θ₀)(-31 + 28θ₁) = 31² - 31*28(θ₀ + θ₁) + 6*28² = 961 + 868 + 4704 = 6533 = 47*139.


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

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

(5) But, then (1 - α + α²¹) doesn't divide 47 and (1 - α + α²¹) 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 139²² and likewise, 47*139 does not divide 47²².

(6) And this violates Euclid's Lemma since (1 - α + α²¹) 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 - α + α²¹) = (1 - α + α²¹)*(1 - α² + α²¹)*...*(1 - α²¹ + α²¹) = 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 α²³=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 α²³ = 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(α) = a₀ + a₁α + ... + a_λ-1α^λ-1

where a_i 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 a₀ + a₁α + ... + 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 p^f ≡ 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 u_i such that η_i ≡ u_i (mod p) [See Corollary 3.1, here]

So u_i which is in the list from 1, 2, ..., p means that η_i - u_i 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 - η₁)(2 - η₁)*...*(p - η_e)

Assuming, of course, that 1 - η₁, 2 - η₁, 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(α) = a₀ + a₁α + a₂α²

In this case, the primitive root is 2 since 2¹ ≡ 2 (mod 3), 2² ≡ 1 (mod 3), and 2³ ≡ 2 (mod 3).

We can then see that σf(α) = a₀ + a₁α² + a₂α⁴ = a₀ + a₁α² + a₂α

We can see that σ²f(α) = σ(a₀ + a₁α² + a₂α) = a₀ + a₁α + a₂α²

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(α)σⁱ[ψ(η)_p] ≡ h(α)σⁱ[ψ(η)_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(α)σⁱ[ψ(η)_p] ≡ 0 (mod pⁿ) 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)ⁿ)

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(α²)*...*g(α^λ-1) divides h(α)*g(α²)*...*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(α²)*...*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(α²)*...*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(α²)*...*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 g₁(α) and g₂(α), then it is true for the product, g₁(α)*g₂(α)

(12) So, let us assume that all the prime divisors which divide g₁(α)*g₂(α) also divide h(α)

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

h(α) = g₁(α)*h₁(α)

(14) By assumption, every divisor of g₂(α) divides h₁(α).

(15) Since we are assuming that the theorem holds true for g₂(α), then it follows that g₂(α) divides h₁(α) and there exists h₂(α) such that:

h₁(α) = g₂(α)*h₂(α)

(16) Therefore h(α) = g₁(α)g₂(α)h₂(α) we have shown that h(α) is divisible by g₁(α)g₂(α)

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.