Cyclotomic Integers: Principal and Equivalent Divisors

Today's blog is taken straight from Harold M. Edwards' Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.

When Ernst Kummer proposed his concept "ideal numbers" (what I have been calling divisors as used by Edwards) to "save" the fundamental theorem of arithmetic, he had to give up something. In Kummer's approach, all cyclotomic integers are characterized by a unique divisor which is composed of a unique set of prime divisors. The cost of this approach is that not all compositions of prime divisors are necessarily divisors. For example, in the case of λ = 23, there is no cyclotomic integer which is divisible once by one of the prime divisors of 47 and not divisible by any other prime divisor of 47.

The idea that not all prime divisors and not combinations of prime divisors are divisors of a cyclotomic integer leads the idea of "principal divisors."

Definition 1: principal

A divisor is said to be principal if there is some cyclotomic integer for which it is the divisor.

Example 1: Ordinary integers

In the ordinary integers, all primes are principal in the sense that each prime corresponds to integer.

Example 2: Cyclotomic integers where λ = 23

In this case, none of the prime divisors of 47 are principal since none of them divide a cyclotomic integer exactly once without the cyclotomic integer being divisible by any other prime divisor of 47.

The challenge then becomes to determine under which conditions a divisor is principal. To analyze this issue, Kummer proposed the idea of equivalence which leads the very important idea of class number (which I will describe in a future blog)

Definition 2: Equivalence

Two divisors A and B are said to be equivalent denoted A ~ B if it is true that a divisor of the form AC is principal when and only when BC is principal.

Example 1:

In the case where a divisor is not principal, it requires another divisor in order to principal. So, for example, if AB is principal but A is not, then there exists a set of divisors let us call them B₁, B₂, etc such that AB₁, AB₂, etc. are all principal. In this circumstance, the divisors B₁, B₂, etc. are said to be equivalent.

NOTE:

This concept of equivalence is presented as an idea that helps to explain under what conditions a product of divisors is principal. To help explore these ideas, I will now review some basic properties of principal and equivalent divisors. These again, are taken straight from Edwards.

Lemma 1: If A and B are both principal, then so is AB

Proof:

(1) A is principal → ∃ a(α) such that A is the divisor of a(α)

(2) B is principal → ∃ b(α) such that B is the divisor of b(α)

(3) So, AB is the divisor for a(α)b(α) which means that AB is also principal.

QED

Lemma 2: If A and B are divisors such that A and AB are both principal, then B is principal.

Proof:

(1) A is principal → ∃ a(α) such that A is the divisor of a(α)

(2) AB is principal → ∃ c(α) such that AB is the divisor of c(α)

(3) Since A divides AB, we know that a(α) divides c(α) so that there exists b(α) = c(α)/a(α) and we know that B is the divisor of b(α)

QED

Lemma 3: A is principal if and only if A ~ I where I is the empty divisor, that is the divisor of 1.

Proof:

(1) Assume A is principal

(2) Then there exists a(α) such that A is the divisor of a(α)

(3) In all cases where IC is principal, it is implies that C is principal which means that in all those cases AC is also principal [By Lemma 1 above]

(4) Assume A~I

(5) If IC is principal then C is principal since IC = C.

(6) IC is principal implies that AC principal. [From A ~ I]

(7) So if AC is principal and C is principal then A is principal [By Lemma 2 above]

QED

Lemma 4: The equivalence relation ~ is reflexive, symmetric, and transitive.

Proof:

(1) ~ is reflexive, that is, A ~ A, since A can always be replaced by itself.

(2) ~ is symmetric since multiplication of divisors is commutative. If AB is principal, then BA is also principal.

(3) ~ is transitive since if A~B and B~C, then A~C. Assume there was a divisor D where AD is principal but CD is not, then BD would not be principal (by B~C) and this would be a contradiction of A~B so this divisor D cannot exist.

QED

Lemma 5: Multiplication of divisors is consistent with the equivalence relations. That is A~B implies AC~BC for all divisors C

Proof:

(1) Assume ACD is principal

(2) Then A(CD) is principal since a divisor can be formed from C,D

(3) Then B(CD) is principal (from A~B)

(4) Assume ACD is not principal

(5) Then A(CD) is not principal since a divisor can be formed from C,D

(6) Then B(CD) is not principal (otherwise, we violate A~B)

QED

Lemma 6: Given any divisor A, there is another divisor B such that AB~I

Proof:

(1) N(A) is the divisor of an integer.

(2) Let B = the complement of N(A), that is, N(A)/A.

(3) Then AB is principal and this leads to AB~I (from Lemma 3 above)

QED

Lemma 7: A ~ B implies there exist principal divisors M and N such that AM = BN.

Proof:

(1) Assume A ~ B

(2) There exists C such that AC is principal. (from Lemma 6 above)

(3) AC ~ I (from Lemma 3 above)

(4) Let M = BC

(5) Let N = AC

(6) So AM = ABC = BN

QED

Lemma 8: A ~ B if and only if there is a third divisor C such that AC and BC are both principal.

Proof:

(1) Assume A ~ B

(2) Then there exists a divisor C such that AC is principal (from Lemma 6 above) and BC is principal.

(3) Assume AC,BC are principal

(4) Then A~B by definition.

QED

Cyclotomic Integers: The Norm of Divisors

Today's content is taken straight from Harold M. Edwards' Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.

Lemma 1: Norm of a Prime Divisor is the number of incongruent cyclotomic integers

If A is a prime divisor, the Norm N(A) can be regarded as a positive integer that is equal to the number of incongruent cyclotomic integers mod A.

Proof:

(1) If A is a prime divisor, then it is either the exceptional prime divisor (α - 1) or it is one of e prime divisors that divide p.

(2) Assume A = α - 1

(3) Then ever cyclotomic integer is congruent to one and only one of the λ integers 0, 1, 2, ..., λ-1.

(4) And N(α-1) = λ (see Lemma 6, here for details)

(5) Assume A ≠ α - 1.

(6) Then its norm is p^f where p is the prime integer that it divides and f is the exponent of p mod λ.

The norm of a divisor is defined to be A*σA*σ²A*...*σ^λ-2A = (A*σA*σ²A*..*σ^e-1A)(σ^eA*...*σ^2e-1A)....(σ^λ-e-1A*..*σ^λ-2A)

Now, each of these set of e prime divisors is the same as p. Likewise, ef = λ - 1.

This gives us:

(p)*...*(p) = p^f.

(7) Using a previous result (see Theorem 3, here), we know that there are p^f incongruent elements mod A.

QED

Lemma 2: Norm of a Power of a Prime Divisor is the number of incongruent cyclotomic integers

If A is a power of a prime divisor, the norm N(A) can be regarded as a positive integer that is equal to the number of incongruent cyclotomic integers mod A.

Proof:

(1) Let A = Pⁿ where P is a prime divisor.

(2) Let ψ(α) be a cyclotomic integer which is divisible by P with multiplicity exactly 1 but not divisible at all by any of the conjugates of P. [See Proposition 1, here for details on this construction if needed]

(3) Each cyclotomic integer is congruent to one of the form a₀ + a₁ψ(α) + a₂ψ(α)² + ... + a_n-1ψ(α)^n-1 mod Pⁿ and two cyclotomic integers of this form are congruent if and only if the coefficients a₀, a₁, ..., a_n-1 are the same mod P since:

(a) When n=1, this is obvious since we are only dealing with a₀.

(b) Assume that it is proven for n-1.

(c) Then, for a given cyclotomic integer x(α), there are cyclotomic integers a₀, a₁, ..., a_n-2 for which x(α) ≡ a₀ + a₁ψ(α) + ... + a_n-2ψ(α)^n-2 (mod P^n-1) and the coefficients a₀, a₁, ..., a_n-2 are uniquely determined mod P. [By our assumption in step (b)]

(d) Let y(α) = x(α) - a₀ - a₁ψ(α) - ... - a_n-2ψ(α)^n-2.

(e) Then y(α) ≡ 0 mod P^n-1 [By combining step (c) and step (d)]

(f) Now, we need to prove that y(α) ≡ aψ(α)^n-1 mod Pⁿ for some a and that a is uniquely determined mod P.

(g) Let γ(α) denote the the product of e-1 distinct conjugates of ψ(α) so that γ(α)ψ(α) = pk where k is an integer relatively prime to p.

We know that p divides γ(α)*ψ(α) exactly once so k is what is left over. Since p is a prime, we know that gcd(p,k)=1.

(h) So if we multiply γ(α)^n-1 to both sides of (f), we get:

y(α)γ(α)^n-1 ≡ aγ(α)^n-1ψ(α)^n-1 ≡ ap^n-1k^n-1 (mod Pⁿ)

(i) Since gcd(p,k)=1, there exists an integer m such that mk ≡ 1 (mod p).

NOTE: This comes straight from Bezout's Identity which says there exist m,n such that mk + np = 1. In other words (-n)p = mk - 1.

(j) Multiplying m^n-1 to both sides of (h) gives us:

y(α)γ(α)^n-1m^n-1 ≡ ap^n-1k^n-1m^n-1 ≡ ap^n-1 (mod Pⁿ)

(k) Since y(α) ≡ 0 (mod P^n-1) by assumption, then y(α)γ(α)m^n-1 is divisible by p^n-1

(l) This shows that y(α) is determined by a mod P [See here for details if needed]

(m) This completes the proof in the case A = Pⁿ.

(4) This proves that the number of classes mod Pⁿ is equal to the number of ways of choosing a₀, a₁, ..., a_n-1 mod P which is N(P)ⁿ = N(Pⁿ).

QED

Theorem 1: Norm of a Divisor is the number of incongruent cyclotomic integers

If A is a divisor, the Norm N(A) can be regarded as a positive integer that is equal to the number of incongruent cyclotomic integers mod A.

Proof:

(1) The number of incongruent elements mod AB (where A,B are relatively prime) is never more than the number of incongruent elements mod A times the number of incongruent elements mod B since:

(a) Let x ≡ x' (mod A)

(b) Let x ≡ x' (mod B)

(c) Then:

A divides x - x'

B divides x - x'

(d) Since A,B are relatively prime, this means that AB divides x - x'.

(e) So that x ≡ x' (mod AB)

(2) The Chinese Remainder Theorem for Divisors (see here) shows that all possible classes mod A and mod B occur.

(3) So that, the number of classes mod AB is equal to the number of classes mod A times the number of classes mod B.

(4) By induction, if A,B,C,D are relatively prime divisors, then the number of classes mod ABC*..*D is equal to number of classes mod A times ... times the number of classes mod D.

(5) If A,B,C,D are powers of prime divisors, by Lemma 2 above this number is equal to N(A)*N(B)*N(C)*...*N(D) = N(ABC*...*D).

(6) Since any divisor can be written in the form A*B*C*....*D where A,B,C,...,D are relatively prime powers of prime divisors, it follows that the number of classes mod any divisor is the norm of that divisor.

QED

Cyclotomic Integers: Chinese Remainder Theorem for Divisors

Today's blog shows how we are able to generalize the Chinese Remainder Theorem (see here for a review of the Chinese Remainder Theorem for integers) to apply to cyclotomic integer divisors (see here for my notes from Edwards on divisors, see here for a review of cyclotomic integers).

The details behind today's proof are taken from Harold M. Edwards Fermat's Last Theorem: A Genetic Introduction to Algebraic Integer Theory.

Lemma 1: Criterion for Chinese Remainder Theorem

Let A and B be relatively prime divisors and let a(α) and b(α) be cyclotomic integers.

The Chinese Remainder Theorem is proven is there exists cyclotomic integer g(α),h(α) such that:

g(α) ≡ 1 (mod A)
g(α) ≡ 0 (mod B)

h(α) ≡ 1 (mod B)
h(α) ≡ 0 (mod A)

Proof:

(a) Let x(α) = g(α)a(α) + h(α)b(α)

(b) x(α) satisfies the conditions of the Chinese Remainder Theorem since:

x(α) ≡ (1)a(α) + (0)b(α) ≡ a(α) (mod A)

x(α) ≡ (0)a(α) + (1)b(α) ≡ b(α) (mod B)

QED

Lemma 2: There is only one distinct prime divisor that divides λ

For the set of prime divisors derived from λ, p, e, and f (see here fore review of prime divisors), the only prime divisor which divides λ is (α - 1)

Proof:

(1) This lemma is proven if we can show the following:

(a) N(α - 1) = λ [This shows that λ has (α - 1) as a factor]

(b) α - 1 is prime so that (α - 1) divides f(α)g(α) if and only if (α-1) divides f(α) or (α - 1) divides g(α).

(2) N(α - 1) = λ [See Lemma 6, here]

(3) Now, we need to show that if (α - 1) divides f(α)g(α), then (α-1) divides f(α) or (α - 1) divides g(α).

(4) Assume that (α-1) divides f(α)g(α)

(5) So that f(α)g(α) ≡ 0 (mod α - 1)

(6) α ≡ 1 (mod α -1 )

(7) So that f(1)g(1) ≡ 0 (mod α - 1)

This is shown by the following:

(a) Let h(α) = f(α)g(α) so that h(α) ≡ 0 (mod α -1) by step #5.

(b) By definition h(α) = a₀ + a₁α + ... + a_λ-1α^λ-1 where a_i are integers (see here)

(c) So h(1) = a₀ + a₁ + ... + a_{λ - 1}

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

(e) Now, in each case (α - 1) divides (αⁱ - 1) [See here for details if needed]

(f) So that we have:

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

(g) Since h(α) ≡ 0 (mod α - 1), this further gives us:

0 - h(1) ≡ 0 (mod α -1) which tells us that h(1) ≡ 0 (mod α - 1)

(8) Since f(1),g(1) are integers, we know that f(1)g(1) ≡ 0 (mod λ)

This follows from the fact that (α - 1) divides f(1)g(1) → N(α - 1) divides N[f(1)g(1)] [See Lemma 6, here for details]

N[f(1)g(1)] = f(1)^λg(1)^λ

N(α-1) = λ

So in order for λ to divide [f(1)g(1)]^λ, by Euclid's Generalized Lemma, λ would need to divide f(1)g(1).

(9) But then f(1)g(1) ≡ 0 (mod λ) is true if and only if λ divides f(1) or λ divides g(1).

QED

Lemma 3: Chinese Remainder Theorem for Distinct Prime Divisors

If A,B are distinct prime divisors for cyclotomic integers, then the Chinese Remainder Theorem follows.

Proof:

(1) Let λ be a prime integer. Let α be a primitive root of unity where α^λ = 1 and α is the least positive integer where this is true. Let e,f be integers such that ef=λ-1. Let p_A,p_B be prime integers.

(2) Based on the definition of prime divisors for cyclotomic integers (see here for review of prime divisors), we can say:

Let A be a prime divisor which is derived from λ, p_A, f, and e.

Let B be a prime divisor which is derived from λ, p_B, f, and e.

(3) We can assume that p_A = p_B since if p_A ≠ p_B, then we can apply the Chinese Remainder Theorem for integers (see here) to derive an integer x that satisfies the Chinese Reaminder Theorem for prime divisors. This means that we only need to prove the case where p_A = p_B.

(4) From step #3, we know that p_A ≠ λ since λ is only divisible by one prime divisor (α -1) [see Lemma 2 above] and since p_A = pB implies that p_A is divisible by two distinct primes (A,B).

(5) Since, p_A ≠ λ, we can apply a previous result (see Theorem 1, here) so that we know that there exists a cyclotomic integer ψ such that:

ψ ≡ 0 (mod B)

ψ not ≡ 0 (mod A)

(6) From a previous result (see Corollary 2.1, here), result we know that there are (p_A)^f distinct congruence classes mod A.

So that we have:

a₁, a₂, ..., a_ν where ν = (p_A)^f

We also know that for any cyclotomic integer f(α), we can assume that:
f(α) ≡ a_i (mod A)

(7) We also know that ψ(α)a_i forms a set of ν distinct congruent classes:

ψ(α)a₁, ψ(α)a₂, ..., ψ(α)a_ν (mod A)

since:

(a) Assume there exists i,j such that:

ψ(α)a_i ≡ ψ(α)a_j (mod A)

(b) Then by definition of mod (see here for review if needed)

The divisor A divides ψ(α)a_i - ψ(α)a_j.

This means that:

ψ(α)(a_i - a_j) ≡ 0 (mod A)

(c) Now since A is a prime divisor (see here for review) and since ψ(α) not ≡ 0 (mod A), we can conclude that:

a_i - a_j ≡ 0 (mod A) which means that i = j since by step #6, we know that i ≠ j, then a_i - a_j not ≡ 0 (mod A) since each a_i is a distinct congruence class.

(d) So from step #a, we see that if a_i not ≡ a_j, then ψ(α)a_i not ≡ ψ(α)a_j.

In other words, there is no overlap and ψ(α) forms a mapping that preserves the distinct congruence classes.

(8) From step #6, we know that there exists an integer i such that a_i ≡ 1 (mod A).

(9) From step #7, we know that there exists an integer j such that ψ(α)a_j ≡ a_i ≡ 1 (mod A).

(10) Let g(α) = ψ(α)a_j so that:

g(α) ≡ 1 (mod A)
g(α) ≡ 0 (mod B) [From step #5]

(11) We can make the same argument to derive an h(α) such that:

h(α) ≡ 1 (mod B)
h(α) ≡ 0 (mod A)

(12) Applying Lemma 1 above this is enough to establish the Chinese Remainder Theorem.

QED

Lemma 4: Chinese Remainder Theorem for Divisors which are Prime Powers

If A,B are distinct divisors for cyclotomic integers that are powers of prime divisors, then the Chinese Remainder Theorem follows.

Proof:

(1) Since A,B are powers of prime divisors, there exist prime divisors P,Q and integers m,n such that:

A = Pⁿ
B = Q^m

(2) From Lemma 3 above, we know that there is a cyclotomic integer g(α) such that:

g(α) ≡ 1 (mod P)
g(α) ≡ 0 (mod Q)

(3) Let h(α) = g(α)^m

(4) Then,

h(α) ≡ g(α)^m ≡ (0)^m ≡ 0 (mod Q)

If Q divides g(α), then Q^m divides g(α)^m and this means that B divides g(α) so that we get:

h(α) ≡ 0 (mod B).

(5) We can construct a cyclotomic integer ψ(α) such that ψ(α) is divisible by P with multiplicity exactly 1 and not divisible at all by any of the conjugates of P. [See Proposition 1, here for proof]

(6) We can express h(α) in the following form using a₀, ..., a_n-1:

h(α) ≡ a₀ + a₁ψ(α) + ... + a_n-1ψ(α)^n-1 (mod A)

since:

(a) h(α) ≡ a₀ + a₁ψ(α) + ... + a_n-1ψ(α)^n-1 (mod ψ(α)ⁿ)

where a_i are integers.

(b) By step #5, we know that P divides ψ(α) so we know that Pⁿ divides ψ(α)ⁿ which gives us:

h(α) ≡ a₀ + a₁ψ(α) + ... + a_n-1ψ(α)^n-1 (mod A) [Since A = Pⁿ]

(7) h(α) ≡ 1 (mod P) since g(α)^m ≡ 1^m ≡ 1 (mod P).

(8) We can now solve for each a_i by noting:

(a) From step #7, we know that a₀ ≡ 1 (mod P) since P divides ψ(α) from step #6 so we can set a₀=1.

(b) Once can now solve for each a_i since

h ≡ 1 + a₁ψ(α) (mod P²) [Since P divides ψ(α)]

So then set a₁ = (g² - a₀ (mod ψ(α)²))

set a₂ = (g³ - a₀ - a₁ (mod ψ(α)³))

And we can repeat this process up to n-1.

set a_n-1 = (g^n-1 - a₀ - ... - a_n-3 (mod ψ(α)^n-1))

(9) We can also define a function f = b₀ + b₁ψ(α) + ... + b_n-1ψ(α)^n-1

where b₀ = 1, b₁ + a₁b₀=0 , b₂ + a₁b₁ + a₂b₀ = 0, ..., up to b_n-1 + a₁b_n-2 + ... + a_n-1b₀=0.

(10) We can now show that hf ≡ 1 (mod A) since:

(a) hf ≡ b₀ + (b₁ + a₁b₀)ψ(α) + (b₂ + a₁b₁ + a₂b₀)ψ(α)² + ... + (b_n-1 + a₁b_n-2 + ... + a_n-1b₀)ψ^n-1 (mod A).

(b) Now applying the equations used to define b₀, b₁, ..., etc.

we get:

hf ≡ 1 (mod A)

(11) We now have:

hf ≡ 1 (mod A)
hf ≡ 0 (mod B)

QED

Theorem 1: Chinese Remainder Theorem

Let A and B be relatively prime divisors and let a(α) and b(α) be cyclotomic integers. Then there is a solution x(α) of the congruences x(α) ≡ a(α) (mod A) and x(α) ≡ b(α) (mod B)

Proof:

(1) We know by the Fundamental Theorem for Divisors of Cyclotomic Integers that each divisor consists of a product of prime divisors so that:

A = A₁*A₂*...*A_μ

B = B₁*B₂*...*B_ν

where A_i, B_j are all powers of distinct prime divisors.

(3) Using Lemma 4 above, we know that for each A_i in the list A₂, ..., A_μ there exists a cyclotomic integer a_i(α) such that:

a_i(α) ≡ 1 (mod A₁)
a_i(α) ≡ 0 (A_i)

(4) Likewise, for each B_j in the list B₁, ..., B_ν, there exists a cyclotomic integer b_j(α) such that:

b_j(α) ≡ 1 (mod A₁)
b_j(α) ≡ 0 (mod B_j)

(5) Let g₁(α) = a₂(α)*a₃(α)*...*a_μ(α)*b₁(α)*...*b_ν(α)

(6) We can see that

g₁(α) ≡ 1*1*1*....*1 ≡ 1 (mod A₁)

g₁(α) ≡ 0 (mod A_i where i ≠ 1) [Since A_i will divide a_i(α) which means that it divides g₁(α)]

g₁ ≡ 0 (mod B_j) [Since B_j will divide b_j(α) which means that it divides g₁(α)

(7) We can make the construction for each of A_i so that we have: g₁(α), g₂(α), ..., g_μ(α)

Further, we can assume that for each g_i(α) we have:

g_i(α) ≡ 1 (mod A_i)

g_i(α) ≡ 0 (mod A_k where k ≠ i)

g_i(α) ≡ 0 (mod B_j)

(8) Let g(α) = g₁(α) + g₂(α) + ... + g_μ(α)

(9) g(α) ≡ 1 (mod A) since:

For each A_i, we have:

g(α) ≡ g₁(α) + ... + g_i(α) + ... g_μ(α)

And therefore, g(α) ≡ 1 (mod A)

(10) g(α) ≡ 0 (mod B) since:

For each B_j, we have:

g(α) ≡ 0 (mod B_j)

And therefore, g(α) ≡ 0 (mod B)

(11) Using Lemma 1 above, we are done.

QED