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.

Fermat's Last Theorem: Kummer's Proof for Regular Primes

Today's blog is on the proof first presented by Ernst Kummer for regular primes. Before Andrew Wiles, this was the highpoint of the work done on Fermat's Last Theorem.

Kummer himself claimed that he worked on the proof not out of an interest in Fermat's Last Theorem but in generalizing the ideas implicit in quadratic reciprocity (see H. M. Edwards' book). Still, this proof would later serve as an important foundation to the work done by Richard Dedekind in establishing algebraic number theory.

Implicit in the concept of regular primes (see here) is the concept of class number (see here), ideal numbers (see here), and cyclotomic integers (see here). Through out the proof, I have included links to help people review the necessary concepts.

The details of the proof are based on the work done by H. M. Edwards in his book: Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.

Theorem: if x,y,z,n are integers and n is a regular prime, then xⁿ + yⁿ = zⁿ → xyz = 0.

Proof:

(1) From the given, we know that n is a regular prime. [See Definition 1, here]

(2) We can assume that x,y,z are relatively prime. [See here for details]

(3) Let λ = n. [We use λ to represent n just as Kummer did in his original paper, see Definition 1, here for details]

(4) Let α be a primitive root of unity such that αⁱ ≠ 1 when i is less than λ and α^λ = 1 [See here for details on primitive root of unity]

(5) Then, using α, we can refactor xⁿ + yⁿ to get:

z^λ = x^λ + y^λ = (x + y)(x + αy)(x + α²y)*...*(x + α^λ-1y). [See Lemma 1 here for details on this refactoring]

(6) We can assume that all elements (x + αⁱy) in step #4 are either relatively prime or have only α - 1 as a common factor since:

(a) Assume that there exists some prime p that divides both x + αⁱy and x + α^i+ky.

(b) Now, we note that:

(x + α^i+ky) - (x + αⁱy) = α^i+ky - αⁱy = αⁱ(α^k - 1)y

(x + α^i+ky) - α^k(x + αⁱy) = x - α^kx = (α^k - 1)*(-1)*x

(c) So, if p divides x + αⁱy and x + α^i+ky, then p divides both αⁱ(α^k - 1)y and (α^k - 1)*(-1)*x

This is true since if a factor a divides b and c, then a divides (b - c) and a also divides (b-dc).

(d) Now, we note that αⁱ is a unit since αⁱ * α^λ-i = 1 and since -1 is a unit.

This gives us that p divides (α^k - 1)y and (α^k - 1)*x [Since only a unit divides a unit, see here for details on cyclotomic units]

(e) Now, we know that p cannot divide both x,y (since x,y are relatively prime) so p must divide α^k - 1 which means that p = α - 1. [See Lemma 3, here]

(7) If α - 1 divides any of the element of the form (x + αⁱy), then it divides all the other factors of this form since:

(a) if (α - 1) divides (x + αⁱy), then (α-1) divides (x + αⁱ⁺¹y) since:

(x + αⁱ⁺¹y) - (x + αⁱy) = αⁱ⁺¹y - αⁱy = αⁱ(α - 1)y.

In other words, if a factor a divides c and d and b + c = d, then a must divide b.

(b) if (α - 1) divides (x + αⁱy), then (α-1) divides (x + α^i-1y) since:

(x + αⁱy) - (x + α^i-1y) = α^i-1(α - 1)y.

(8) Since there are λ - 1 factors of the form (x + αⁱy), then (α - 1)^λ-1 = λ*unit (see Corollary 3.2, here) gives us that λ divides z^λ which using Euclid's Generalized Lemma (see here) gives us that λ divides z.

(9) Even if λ divides x or y, we can assume that it divides z.

(a) Let's assume that λ divide x. [if λ divides y, we can use the same argument substituting y for x]

(b) Since λ is odd, we know that -(-x)^λ = x^λ and -(-z)^λ = z^λ.

(c) This gives us:

(-x)^λ = yλ + (-z)^λ

(d) Then, if we label (-x)^λ as z' and (-z)^λ as x', then we have shown that if λ divides x,y,or z, we can assume an equation of the form z'^λ = x'^λ + y^λ where λ divides z'^λ

(e) Finally, if λ divides z^λ, then by Euclid's Generalized Lemma, it divides z.

(10) Step #9 is useful because it means that we only have to consider two cases:

Case I: x,y,z,λ are coprime and therefore each factor (a+x^jy) are relatively prime to each other.

Case II: λ divides z.

(11) We can now conclude that Fermat's Last Theorem holds for regular primes since:

(a) Fermat's Last Theorem holds for Case I. [See Theorem, here]

(b) Fermat's Last Theorem holds for Case II. [See Theorem, here]

QED

Fermat's Last Theorem: The Musical

I am still working through the background to Kummer's proof so I don't yet have any mathematics to post.

In the mean time, I was browsing at a mathematics site (Clay Mathematics Institute) and I found out that there was a musical made on Fermat's Last Thereom. It's called Fermat's Last Tango.

You can see behind the scenes clips here.

Fermat's Last Theorem and the Simpson's TV Show

There was recently an article in Science News on the mathematics of the Simpson's. One of the throw away jokes is 1782¹² + 1841¹² = 1922¹².

Read more here if you are interested.

Another False Proof: E. E. Escultura

I must admit that I have a fascination with false proofs. Perhaps, that is why I am so interested in Fermat's Last Theorem.

Because of the many false proofs out there and because so many people are unable to tell the difference between mathematics and pseudomathematics, I have started a new blog track: False Proofs.

This past week I was honored with a long, blog comment from Mr. E. E. Escultura who believes that he has found a flaw in the real number system. The flaw according to Mr. Escultura is the axiom of trichotomy and the solution is to avoid using nonterminating decimals. If you are interested, you can find the details here as well as links to the many other blogs that have features Mr. Escultura's ideas.

Slightly changing this blog

Hi Everyone,

In the past, I've been posting my notes on proofs to this blog. I think that this has made this blog much more difficult to follow and has detracted from my purpose of making the mathematics of Fermat's Last Theorem as accessible as possible.

For this reason, I have created a new subdomain on blogger: Math Notes which I will use for notes as I prepare a complete proof.

I will use this blog for general news, biographies of mathematicians, posting of complete proofs, and general discussion of interesting mathematical topics.

I am hoping that this will make the blog easier to follow and more interesting. I am very glad to hear people's comments for improving this blog.

Thanks,

-Larry

Cyclotomic Integers: Divisibility Test

In today's blog, I continue to review results from Harold Edward's Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory. I am continuing down the same chapter that I started in an earlier blog. If you would like to start at the beginning of cyclotomic integer properties, start here.

Lemma 1: For every cyclotomic prime h(α), there exists a rational prime p such that h(α) divides p.

Proof:

(1) Let h(α) be a cyclotomic prime. [See here for a review of cyclotomic primes]

(2) We know that Nh(α) is a rational integer. [See Lemma 5, here]

(3) By the Fundamental Theorem of Arithmetic, Nh(α) consists of a set of rational primes: p₁*...*p_n.

(4) Since h(α) is a cyclotomic prime, it must divide one of these primes p_i. [See Definition 4, here]

QED

Lemma 2: Every cyclotomic integer g(α) is congruent mod h(α) to a cyclotomic integer of the form a₁α^f-1 + a₂α^f-2 + ... + a_f where a_i are positive integers less than a prime integer p.

Proof:

(1) From a previous result, we know that every cyclotomic integer g(α) can be expressed in the following form:

g(α) = g₁(η)α^f-1 + g₂(η)α^f-2 + ... + g_f(η)

where g_i(η) are cyclotomic integers made up of periods of length f. [See Corollary 3.1, here]

(2) Each cyclotomic integer g_i(η) is congruent mod h(α) to an integer g_i(u) where g_i(u) denotes the integer obtained by substituting u₁ for η₁, u₂ for η₂, etc. [See Corollary 2.1, here]

(3) We know that there exists a rational prime p such that h(α) divides p. [See Lemma 1 above]

(4) We can assume that g_i(u) is between 0 and p-1 since:

(a) Assume that g_i(u) ≥ p.

(b) There exists a value i such that g_i(u) ≡ i (mod p) and i is between 0 and p-1.

(c) But then g_i(u) ≡ i (mod h(α)) since h(α) divides p.

(d) So, we can conclude that g_i(η) ≡ i (mod h(α))

(5) So that putting it all together, we have:

g(α) = g₁(η)α^f-1 + g₂(η)α^f-2 + ... + g_f(η) ≡ g₁(u)α^f-1 + g₂(u)α^f-2 + ... + g_f(u) ≡

≡ a₁α^f-1 + a₂α^f-2 + ... + a_f (mod h(α))

where a_i is between 0 and p-1.

QED

Corollary 2.1: Every cyclotomic integer g(α) is congruent mod h(α) to 1 of p^f specific cyclotomic integers.

Proof:

(1) From Lemma 2 above, every integer g(α) satisfies the equation below:

g(α) ≡ a₁α^f-1 + a₂α^f-2 + ... + a_f (mod h(α)) where a_i is between 0 and p-1.

(2) Now the conclusion follows from noting that each of the f different integers can take p different values which gives us: p^f different values.

QED

Definition 1: Additive group

An additive group is a group defined around the operation of addition. [See here for a review of the concept of a group]

Example: Z₉ is an additive group

Z₉ = { 0, 1, 2, 3, 4, 5, 6, 7, 8 }

It is clear that it has all the properties of a group:

(1) Closure: addition of any two integers modulo 9 results in another integer modulo 9.

(2) Identity: 0 is the identity.

(3) Inverse: For any integer, 9-i is the inverse. For example, 1 + 8 = 0 modulo 9.

(4) Associativity: For any a,b,c ∈ Z₉, we see that:

a + (b + c) = (a + b) + c

Lemma 3: The additive group of cyclotomic integers mod p has p^λ-1 elements.

Proof:

(1) Let λ be an odd prime and let α be a root of unity such that α^λ = 1 but for all positive integers i less than λ, αⁱ ≠ 1. [See here for review of roots of unity]

(2) All cyclotomic integers based on λ can be put into this form:

a₀ + a₁α + a₂α² + ... + a_λ-1α^λ-1

where a_i are all integers [See Lemma 1 here]

(3) Since we are talking about values modulo p, we can assume that a_i is between 0 and p-1.

(4) This means that there are λ-1 elements that can take values of 0 to p-1.

(5) If we count all possible values, this leads us to λ - 1 multiples:

[0..p-1]*[0..p-1]*...*[0..p-1] = p^λ-1

QED

Lemma 4: if h(α) is a cyclotomic prime that divides a rational prime p, then the additive group of cyclotomic integers mod h(α) is a subgroup of the additive group of cyclotomic integers mod p.

Proof:

(1) We know that the set of cyclotomic integers mod p under '+' is an abelian group since:

(a) It is closed on the operation of '+'

(b) 0 mod p is the identity element.

(c) For any cyclotomic integer ≡ r (mod p), the inverse element is p-r.

(d) '+' is clearly associative in nature.

(e) It is abelian since '+' is commutative.

(2) We can make the same arguments to show that the cyclotomic integers mod h(α) is an abelian group on the operation of addition.

(3) To complete this proof, we only need to show that the set of cyclotomic integers mod h(α) is a subset of the cyclotomic integers mod p.

(4) This is the case since:

(a) Let g(α) be a cyclotomic integer.

(b) Then, there exists r(α) such that g(α) ≡ r(α) (mod h(α)) so that r(α) ∈ additive group of cyclotomic integers mod h(α)

(c) Now we can assume r(α) has the following form (see Lemma 1, here):

a₀ + a₁α + ... + a_λ-1α^λ-1

(d) We can further assume that all a_i are between 0 and p-1 since if a_i is greater than p, then there exists a' such that a_i ≡ a' (mod p) where a' is less than p and further if a_i ≡ a' (mod p), then a_i ≡ a' (mod h(α)) because h(α) divides p.

(e) But if all a_i are between 0 and p-1, then r(α) ∈ the additive group of cyclotomic integers mod p.

QED

Definition 2: Exponent of p mod λ

The exponent of p mod λ is the smallest positive integer whereby p^f ≡ 1 (mod λ)

Lemma 5: Let S be the set of cyclotomic integers of the form a₁α^f-1 + a₂α^f-2 + ... + a_f where a_i are positive integers less than p.

Two elements of S are congruent if and only if they are identical.

Proof:

(1) The number of incongruent elements mod h(α) is a power of p, say pⁿ since:

(a) The additive group of cyclotomic integers mod h(α) is a subgroup of the additive group of cyclotomic integers mod p. [See Lemma 4 above]

(b) The additive group of cyclotomic integers mod p has p^λ-1 elements. [See Lemma 3 above]

(c) Since the additive group of cyclotomic integers mod h(α) is a subgroup of the additive group of cyclotomic integers mod p, the order of the first group must divide p^{λ - 1}. [By Lagrange's Theorem, see here]

(d) Because p is prime, the number of elements in the additive group of cyclotomic integers mod h(α) must be a power of p.

(2) The number of incongruent cyclotomic integers mod h(α) is at least λ + 1 because 0, α, α², ..., α^λ=1 are all incongruent mod h(α) since:

(a) Any cyclotomic integer divisible by h(α) must have a norm divisible by p [since p = Nh(α), see Lemma 6 here, and since h(α) divides g(α) → Nh(α) divides Ng(α), see Lemma 6 here]

(b) On the other hand, monomials α^j - 0 have norm = 1 [See Lemma 5, here]

(c) The binomials αⁱ - α^j (where i is not congruent to j mod λ) have a norm equal to N(α-1)=λ [See Lemma 6, here]

(d) Neither 1 nor λ is divisible by p, so none of these cyclotomic integers are divisible by h(α)

(3) The number of nonzero incongruent cyclotomic integers mod h(α) is divisible by λ since:

(a) If α, α², ..., α^λ =1 are all the nonzero cyclotomic integers mod h(α), then there are exactly λ of them.

(b) Assume that there exists a cyclotomic integer ψ(α) such that ψ(α) is not congruent to 0 mod h(α) and ψ(α) is not congruent to α^j mod h(α) for j = 1,2, ..., λ.

(c) Then ψ(α)α, ψ(α)α², ..., ψ(α)α^λ = ψ(α) are all nonzero mod h(α) [because h(α) is prime] and distinct mod h(α) [because ψ(α)α^j ≡ ψ(α)α^k would imply α^j ≡ α^k) and distinct from α, α², ..., α^λ (because ψ(α)α^j ≡ αⁱ would imply ψ(α) ≡ α^k)

(d) If this is all the all the possible nonzero cyclotomic integers congruent to h(α), then there are 2λ of them.

(e) Eventually, we run out of possibilities. Let us say that this happens after m such iterations of step (#3c).

(f) Then, there are mλ distinct nonzero cyclotomic integers mod h(α)

(4) From step #1, we get that the total number of nonzero distinct cyclotomic integers mod h(α) is pⁿ - 1.

(5) So putting #4 with #3, we get:

mλ = pⁿ - 1.

(6) This gives us that:

pⁿ ≡ 1 ( mod λ)

(7) Since f is the exponent of p mod λ, (see definition 2 above), we know that n ≥ f. [We know that f ≠ 0 since pⁿ is greater than λ + 1. ]

(8) Thus, the number of pⁿ of incongruent elements mod h(α) is at least p^f.

QED

Corollary 5.1: To test for divisibility by h(α), it is not necessary to know h(α) but only the integers u_i where i is between 1 and e and for which η_i ≡ u_i (mod h(α)) for all i between 1 and e.

Proof:

(1) We know that a cyclotomic integer g(α) is divisible by h(α) if g(α) ≡ 0 (mod h(α))

(2) For any cyclotomic g(α), we know that it is congruent to a cyclotomic integer of the form a₁α^f-1 + a₂α^f-2 + ... + α^f (mod h(α)) [See Lemma 2 above]

(3) We can now use Lemma 5 above to test for divisibility.

QED

Cyclotomic Integers: Generalizing Periods

In today's blog, I continue to review results from Harold Edward's Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory. I am continuing down the same chapter that I started in an earlier blog. If you would like to start at the beginning of cyclotomic integer properties, start here.

Lemma 1: Any arbitary cyclotomic integer g(α) of degree f-1 or less can be expressed in terms of cyclotomic integers made up of periods of length f such that:

g(α) = g₁(η)α^f-1 + g₂(η)α^f-2 + ... + g_f(η)

where g₁(η), g₂(η), ..., g_f(η) are cyclotomic integers made up of periods of length f. [See Definition 2 here for review of cyclotomic integers made up of periods of length f]

Proof:

(1) Let g(α) be a cyclotomic integer of degree f-1 so that:

g(α) = a₀ + a₁α + a₂α² + ... + a_f-1α^f-1

(2) Let's define the following polynomials made up of periods of length f [letting e = (λ-1)/f]:

Let g_f(η) = a₀ + (0)η₀ + (0)η₁ + ... + (0)η_e-1

Let g_f-1(η) = a₁ + (0)η₀ + (0)η₁ + ... + (0)η_e-1

and so on until:

Let g₁(η) = a_f-1 + (0)η₀ + (0)η₁ + ... + (0)η_e-1

(3) With the values in (step #2), we see that:

g(α) = g₁(η)α^f-1 + g₂(η)α^f-2 + ... + g_f(η)

QED

Lemma 2: If g(α), h(α), and i(α) are cyclotomic integers expressible in terms of cyclotomic integers made up of periods of length f,

then g(α)h(α) + j(α) is expressible in terms of cyclotomic integers made up of periods of length f.

Proof:

(1) Since g(α), h(α), and j(α) are expressible in terms of cyclotomic integers made up of periods of length f, we have:

g(α) = g₁(η)α^f-1 + g₂(η)α^f-2 + ... + g_f(η)

h(α) = h₁(η)α^f-1 + h₂(η)α^f-2 + ... + h_f(η)

j(α) = j₁(η)α^f-1 + j₂(η)α^f-2 + ... + j_f(η)

where where g₁(η), g₂(η), ..., g_f(η), h_i(η), j_i(η) are cyclotomic integers made up of periods of length f.

(2) We know that the sum of two cyclotomic integers expressible in terms of cyclotomic integers made up of periods of length f is itself expressible in terms of cyclotomic integers made up of periods of length f.

If s(α) = g(α) + h(α) then we can define the following:

For each g_i(η), h_i(η), we have:

g_i(η) = a₀ + a₁η₀ + ... + a_fη_f-1

h_i(η) = b₀ + b₁η₀ + ... + b_fη_f-1

And we can define s_i(η) such that:

s_i(η) = (a₀ + b₀) + (a₁ + b₁)η₀ + ... + (a_f + b_f)η_f-1

(3) The product of g(α)*h(α) is also expressible in terms of cyclotomic integers made up of periods of length f since:

g(α)h(α) = [g₁(η)α^f-1 + g₂(η)α^f-2 + ... + g_f(η)][h₁(η)α^f-1 + h₂(η)α^f-2 + ... + h_f(η)] =

= [g₁(η)α^f-1][h₁(η)α^f-1] + ... + [ g_f(η) ][h_f(η)]

Since the product of two cyclotomic integers made up periods of length f is itself made up of periods of length f (see Corollary 4.1 here), we can conclude that the product of g(α)h(α) is itself a sum of cyclotomic integers made up of periods of length f.

Now from this sum and from the result in step #2, we are done.

QED

Lemma 3: There exists a function p(x) such that:

p(α) = α^f + φ₁(η)α^f-1 + ... + φ_f-(η)α + φ_f(η) = 0

where φ₁(η), φ₂(η), ..., φ_f(η) are cyclotomic integers made up of periods of length f.

Proof:

(1) Let λ be an odd prime.

(2) Let α be a primitive root of unity such that λ is the least positive integer whereby α^λ = 1.

(3) Let e,f be positive integers such that e is a factor of λ - 1 and f = (λ - 1)/e.

(4) Let p(x) be a function such that:



NOTE: In other words, p(x) = (x - σ^eα)(x - σ^2eα)*...*(x - σ^feα)

For review of σ notation, see here.

(5) If we multiply all of the products together, we get the following form:

p(x) = x^f + φ₁(η)x^f-1 + ... + φ_f-(η)x + φ_f(η)

where φ(η) is a cyclotomic integer.

(6) We note that σ^ep(x) = p(x) since:

(a) σ^ep(x) = (x - σ^2eα)(x - σ^3eα)*...*(x - σ^efeα)

(b) σ^efe = σ^eσ^ef = σ^eσ^λ-1 = σ^e [Since ef = λ - 1 by step #3 above and σ^λ-1 is identity from here]

(c) Combining (a) and (b) gives us:

σ^ep(x) = (x - σ^2eα)(x - σ^3eα)*...*(x - σ^eα)

(7) From a previous result (see Lemma 4 here), we know that p(x) must consist of periods of length f so that taking our result from step #5:

p(x) = x^f + φ₁(η)x^f-1 + ... + φ_f-(η)x + φ_f(η)

We know that φ₁(η), φ₂(η), ..., φ_f(η) must all be cyclotomic integers made up of periods of length f.

(8) Now we know that p(α) = 0 since:

(a) p(α) = (α - σ^eα)(α - σ^2eα)*...*(α - σ^feα)

(b) fe = λ - 1 (from step #3)

(c) σ^λ-1 is the identity (see here) so that σ^λ-1α = α

(d) Applying #8b and #8c to (a) gives us:

p(α) = (α - σ^eα)(α - σ^2eα)*...*(α - σ^feα) =

=(α - σ^eα)(α - σ^2eα)*...*(α - α) =

= (α - σ^eα)(α - σ^2eα)*...*(0) = 0

(9) So putting this all together gives us:

p(α) = α^f + φ₁(η)α^f-1 + ... + φ_f-(η)α + φ_f(η) = 0

QED

Corollary 3.1: Every cyclotomic integer g(α) can be expressed in terms of cyclotomic integers made up of periods of length f such that:

g(α) = g₁(η)α^f-1 + g₂(η)α^f-2 + ... + g_f(η)

where g₁(η), g₂(η), ..., g_f(η) are cyclotomic integers made up of periods of length f.

Proof:

(1) Let g(α) be a cyclotomic integer such that:

g(α) = a₀ + a₁α + a₂α² + ... + a_λ-1α^λ-1

NOTE: See Lemma 1 here for details on why all cyclotomic integers can be expressed in this form.

(2) We can restate g(α) in terms of g(x) so that:

g(x) = a₀ + a₁x + a₂x² + ... + a_λ-1

(3) Let p(x) be a polynomial such that:

p(x) = x^f + φ₁(η)x^f-1 + ... + φ_f-1(η)x + φ_f(η)

where φ(η) is a cyclotomic integer.

(4) Using Division by Polynomials (see here) we know that there exists q(x),r(x) such that:

g(x) = q(x)(x^f) + r(x) where degree of r(x) is less than f or r(x) = 0.

(5) Now from Lemma 1 above, we know that r(α) is expressible in terms of cyclotomic integers made up of periods of length f.

(6) Since p(α) = 0 (see Lemma 3 above), we know that α^f is expressible in terms of cyclotomic integers made up of periods of length f since:

α^f = -φ₁(η)x^f-1 - ... - φ_f-1(η)x - φ_f(η)

(7) For now, let's assume that q(x) is of degree less than f.

(8) Then we can apply Lemma 1 above and conclude that q(x) is expressible in terms of cyclotomic integers made up of periods of length f.

(9) Now since g(α) = q(α)(α^f) + r(α), we can apply Lemma 2 above to conclude that g(α) is expressible in terms of cyclotomic integers made up of periods of length f.

(10) Now let's assume that q(α) is of degree f.

(11) Using q(x), we can again apply the Division Algorithm for Polynomials to get:

q(x) = q₁(x)(x^f) + r(x)

Since we are assuming q(x) has a degree of f, it follows that q₁(x) will have a degree less than f.

(12) Using Lemma 2 above, we can conclude that q(α) is expressible in terms of cyclotomic integers since q₁(α), α^f, and r(α) are expressible in terms of cyclotomic integers made up of periods of length f.

(13) Using the Principle of Induction, we can now conclude that this works regardless of the degree of q(α). [Since q(α) with degree f-1 works and since q(α) with degree f-1 working implies that a q(α) with degree f works]

(14) So, using Lemma 2 above, since q(α), r(α), and α^f are expressible in terms of cyclotomic integers made up of periods of length f, so is g(α) since:

g(α) = q(α)α^f + r(α)

QED

Example:

Let λ = 5, f = 2, and γ = 2

So e = (λ - 1)/f = 4/2 = 2

Let g(α) = α⁴ + 2α³ + 3α² + 4α + 5

We note that:

2¹ ≡ 2 (mod 5)
2² ≡ 4 (mod 5)
2³ ≡ 3 (mod 5)
2⁴ ≡ 1 (mod 5)

In this case,

p(x) = (x - σ^eα)(x - σ^2eα)

Now σ^eα = α^γ2 = α⁴

σ^2eα = α^γ4 = α

So,

p(x) = x² - x(α⁴ + α) + α⁵ = x² - x(α⁴ + α) + 1.

We see that p(α) = 0 since:

p(α) = α² - α(α⁴ + α) + 1 = α² - 1 + α² + 1 = 0

So that:

α² = α(α⁴ + α) - 1

Let g(x) = x⁴ + 2x³ + 3x² + 4x+ 5

Now, let's express each of these terms in terms of cyclotomic integers made up of periods of length f=2:

with:
η₀ = α⁴ + α

η₁ = α³ + α²

(η₀)² = α³ + α² + 2.

(η₀)(η₁) = η₀ + η₁

Using the Division Algorithm for polynomials, we see that:

g(x) = q(x)(x²) + r(x)

where:

q(x) = x² + 2x + 3

r(x) = 4x + 5

x² = x(α⁴ + α) - 1

and:

q(α) = [α(α⁴ + α) - 1] + [2α + 3] = α(η₀ + 2) + (2)

r(α) = 4α + 5 = α(4) + (5)

α² = [α(α⁴ + α) - 1] = α(η₀) + (-1)

Then

g(α) = q(α)α² + r(α) =

= α²(η0² + 2η₀) + α(2η₀) + α(-η₀ - 2) -2 + α(4) + (5) =

= [α(η₀) -1](3η₁ + 2) + α(η₀ +2) + (3) =

= α(4η₀ + 3η₁+ 4) + (-3η₁ + 1)

So, let:

g₁(η) = 4η₀ + 3η₁ + 4

g₂(η) = -3η₁ + 1

And finally, this gives us:

g(α) = g₁(η)α + g₂(η)