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

Cyclotomic Integers: Conjugations and the norm of a divisor

Definition 1: σ(p,ψ(η))

σ(p,ψ(η)) = (p,σψ(η))

NOTE: In other words, if A is a prime divisor for a prime p, then σA divides g(α) implies that g(α)σψ(η) ≡ 0 (mod p).

Proposition 1:

Let σⁱ be a conjugation of cyclotomic integers, let g₁(α), g₂(α) be cyclotomic integers, and let A be a divisor.

Then, to say g₁(α) ≡ g₂(α) mod σⁱA is equivalent to saying σ^-ig₁(α) ≡ σ^-ig₂(α) mod A.

Proof:

(1) If A is a power of a prime divisor, say A = P^ν, and if σA divides g(α), then p^ν divides g(α)*σψ(η)^ν

By definition, we say that P^ν divides g(α) if g(α)ψ(η)^ν ≡ 0 (mod p^ν)

By σA divides g(α), we mean that g(α)σψ(η)^ν ≡ 0 (mod p^ν)

(2) This implies that p^ν divides σ^-1g(α)*ψ(η)^ν.

(a) g(α)σψ(η)^ν ≡ 0 (mod p^ν) means that g(α) is divisible by a conjugate to P which is σ¹P.

(b) This is the same as saying that σ^-1g(α) is divisible by P.

(3) Therefore it shows that A divides σ^-1g(α).

This follows since A dividing a cyclotomic integer is the same as showing σ^-1g(α)ψ(η)^ν ≡ 0 (mod p).

(4) If A,B are relatively prime and σ(AB) = σ(A)σ(B) divides g(α) then both σ(A) and σ(B) divide g(α), both A and B divide σ^-1g(α), and therefore, AB divides σ^-1(α).

This is the same reasoning as in step #3.

(5) This shows that, for any A, g(α) ≡ 0 (mod σA) implies σ^-1g(α) ≡ 0 (mod A).

(6) Then, g(α) ≡ 0 (mod σⁱA) implies σ^-1g(α) ≡ 0 (mod σ^i-1A), ...., σ^-ig(α) ≡ 0 (mod A).

(7) Conversely, σ^-ig(α) ≡ 0 (mod σ^λ-1-i(σⁱA)) implies g(α) = σ^-(λ-1)+iσ^-ig(α) ≡ 0 (mod σⁱA).

(8) Thus, (g₁ - g₂) ≡ 0 (mod σⁱA) is equivalent to σ^-i(g₁ - g₂) ≡ 0 (mod A), as was to be shown.

QED

Proposition 2:

If A is any divisor, there is a positive integer whose divisor is equal to the norm of A.

Proof:

(1) The norm of a divisor is defined to be:

A*σA*σ²A*...*σ^λ-2A.

(2) From this definition, it is easy to see that the norm of a product is the product of norms.

(3) So, that this theorem is proven if we can show that it is true for prime divisors.

(4) By the nature of the prime divisor, we know that it is divisor for an odd prime p so we are done.

QED

Cyclotomic Integers: Terminology

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.

Thereom 1:

Let A and B be divisors. If every cyclotomic integer divisible by A is also divisible by B, then A is divisible by B.

Proof:

(1) Let p₁, p₂, ..., p_n be the prime integers that are divisible by the prime divisors which divide A.

In other words, the p's are the prime factors of the norm of A. [This is explained later in the section on norms of divisors]

(2) Let A = A₁, A₂, ..., A_n be a decomposition of A as a product of divisors A_i such that A_i contains all prime divisors in A which divide p_i.

(3) Since a sufficiently high power of p₁, p₂, ... p_n is divisible by A it must, by assumption, be divisible by B.

NOTE: By assumption, we know that ∏ p_i is divisible by each prime divisor of A. If we raise this product to a sufficiently high power, then we know that each prime divisor of A will divide at the appropriate multiplicity. Without assuming a sufficiently high power, we cannot assume that this is the case.

(4) This shows that every prime divisor in B divides one of the p_i and therefore that B can be decomposed as a product B = B₁B₂*...*B_n in which B_i contains all prime divisors in B which divide p_i

Some of the B_i may be I since it may be possible that that a given p_i is not otherwise divisible by any of the divisors of B.

(5) Since the order of the p's is arbitrary, it will suffice to prove that B₁ divides A₁

We can then make the same argument for each B_i, A_i for p_i.

(6) If p₁ = λ, then A₁ = (α - 1)^μ for μ

(7) Then the cyclotomic integer (α - 1)^μ(p₂p₃*...*p_n)^ν is divisible by A for all sufficiently large ν

(8) Therefore it is also divisible by B for large ν.

(9) This implies because B₁ does not divide (p₂p₃*...*p_n)^ν at all, that B₁ divides the cyclotomic integer (α - 1)^μ

Again, since p₁ = λ by assumption, we know that the other p_i do not.

(10) Therfore B₁ divides the divisor of (α - 1)^μ, which is A₁.

(11) If p₁ ≠ λ, let f be the exponent of p₁ mod λ and let ψ be a cyclotomic integer made up of periods of length f which is divisible by one of the e = (λ - 1)/f prime divisors of p₁ with multiplicity 1 and is not divisible at all by the remaining e-1.

(12) Then one can form a product of conjugates of ψ, call it x, with the property that the divisor of x is A₁ times prime divisors which do not divide p₁.

(13) Now x(p₂p₃*...*p_n)^ν is divisible by A for large ν

(14) Therefore it is divisible by B₁.

(15) Since B₁ does not divide (p₂p₃*...*p_n)^ν at all, it follows that B₁ divides the divisor of x.

(16) Since the divisor of x is A₁ times a factor that contains none of the prime divisors of p₁ (and a fortiori none of the prime divisors of B₁) B₁ divides A₁ as was to be shown.

QED


Corollary:

If A and B are divisors and if the relation g₁(α) ≡ g₂(α) mod A" is equivalent to "g₁(α) ≡ g₂(α) mod B" (that is, one relation holds if and only if the other does), then A=B.

Proof:

This follows form the the Theorem above since if A divides B and B divides A then A = B.

QED

Cyclotomic Integers: Divisors

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.

Definition 1: Divisor of a nonzero cyclotomic integer

The divisor of a nonzero cyclotomic integer g(α) is a list, with multiplicities, of all the prime
divisors which divide g(α)

Definition 2: Empty list divisor

A divisor is any finite list of prime divisors. The empty list is considered to be a divisor. The empty list is a the divisor of the cyclotomic integer 1.

Definition 3: product of two divisors

The product of two divisors is the juxtaposition of the two lists counted with multiplicities.

Definition 4: Divisible by a divisor

A cyclotomic integer is said to be divisible by a given divisor if it can be written as a product of that divisor with another divisor. A cyclotomic integer is said to be divisible by a divisor if its divisor is divisible by that divisor and similarly a divisor is said to be divisible by a cyclotomic integer if it is divisible by the divisor of the cyclotomic integer.

NOTE: With these definitions, the fundamental theorem becomes the statement g(α) divides h(α) if and only if the divisor of g(α) divides the divisor of h(α)

Observation: The divisor of a product is the product of the divisors.

Observation: Since 0 is divisible by every nonzero cyclotomic integer, it is sometimes convenient to consider 0 to have the divisor which contains every prime divisor an infinite number of times.

Theorem 1:

Given a prime divisor of p ≠ λ there is a cyclotomic integer ψ(η) made up of periods of length f (the exponent of p mod λ) which is divisible exactly once by that prime divisor of p and which is not divisible by the remaining e-1 prime divisors of p. Consequently, a cyclotomic integer g(α) is divisible with multiplicity μ by the given prime divisor of p if and only if g(α)[σψ(η)]^μ[σ²ψ(η)]^μ*...*[σ^e-1ψ(η)]^μ is divisible by p^μ

Proof:

(1) Let ψ(η) correspond as before to a given prime divisor of p.

That is, let u₁, u₂, ..., u_e be the integers such that u_i - η_i is divisible by the given prime divisor and let ψ(η) be the product of ep-e factors j - η_i in which j ≠ u_i.

(2) Then ψ(η) is divisible by all e prime divisors of p except the given one.

(3) Let φ(η) = σψ(η) + σ²ψ(η) + ... + σ^e-1ψ(η).

(4) φ(η) is divisible by the given prime divisor of p (each term of the sum is divisible by it) but not divisible by the remaining e-1 prime divisors of p (for each of these all but one of the terms are divisible by it but that one is not divisible).

NOTE: The reason this is true is that the σ function shifts the η_i value. So while u_j - η_i is included in ψ(η), when we apply σ to it, we get u_j - η_j. In other words, since we are including all possible shifts as part of the sum, one of these shifts results in a difference which is divisible by p.

(5) If φ(η) is divisible with multiplicity exactly one by the given prime divisor of p, then ψ(η) = φ(η) has the required properties.

(6) If φ(η) is divisible with multiplicty greater than one, then set ψ(η) = φ(η) + p.

(7) Then, ψ(η) is not divisible by the e-1 prime divisors other than the given one (because if it were then φ(η) = ψ(η) - p would be), it is divisible by the given prime divisor of p (because φ(η) is), and it is not divisible with multiplicity greater than one (because if it were then p = ψ(η) - φ(η) would be).

(8) This completes the construction of ψ(η).

(9) The second statement of the theorem is an immediate consequence of the fundamental theorem.

QED

Theorem 2:

The cyclotomic integers called "prime" in the examples earlier are indeed prime. More generally, if p ≠ λ is a prime whose exponent mod λ is f and if g(α) is a cyclotomic integer whose norm is p^f then g(α) is prime. [If g(α) = g(η) is made up of periods of length f then the condition Ng(α) = p^f can also be stated in the form g(η)*σg(η)*...*σ^e-1g(η) = ± p.]

Proof:

(1) Let ν₁, ν₂, ...., ν_e be the exact multiplicities with which the prime divisors of p divide g(α).

(2) Then σg(α) is divisible with the multiplicities ν₂, ν₃, ...., ν_e, ν₁ exactly.

NOTE: This is true since σg(α) just shifts the prime divisors. (See Theorem 4, here)

(3) Then σ²g(α) is divisible with the multiplicities ν₃, ν₄, ...., ν₁, ν₂ exactly and so forth.

NOTE: Same reason as in step #2.

(4) Therefore, each prime divisor of p divides Ng(α) with multiplicity exactly (ν₁ + ν₂ + ... + ν_e)f.

NOTE: We know this since in the given, Ng(α) = p^f.

(5) If Ng(α) = p^f, then one ν_i must be 1 and the others 0.

NOTE: We know this since by our given (ν₁ + ν₂ + ... + ν_e)f= f since Ng(α) = p^f.

(6) Then, by the fundamental theorem, divisibility by g(α) coincides with divisibility by a prime divisor and it follows that g(α) is prime.

QED

Definition 5: greatest common divisor of p

Let a prime divisor of p be given and let ψ(η) be a cyclotomic integer as in the theorem above such that it is made up of periods of length f (the exponent of p mod λ) which is divisible just once by the prime divisor of p in question and not divisible by any of the remaining e-1 prime divisors of p. Then the given prime divisor wil be designated (p,ψ(η)). Since this divisor divides p and ψ(η), both with multiplicity exactly one, and no other prime divisor divides both, (p,ψ(η)) is the greatest common divisor of p and ψ(η).

Definition 6: Empty Divisor

The empty divisor which divides 1 will be denoted by I and an exponent of 0 on a divisor A will be defined to mean A⁰ = I.

Cyclotomic Integers: The Fundamental Theorem

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.

Theorem: The Fundamental Theorem for Cyclotomic Integers

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 1.1: 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 and know that we have 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.