Cyclotomic Integers: Division Algorithm

Today's blog continues the discussion of Kummer's proof of Fermat's Last Theorem for regular primes. If you would like to review the historical context for this proof, start here.

Today, I will continue reviewing the basic properties of cyclotomic integers. Today's content comes directly from Chapter 4 of Harold M. Edwards' Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.

Lemma 1: Criteria for division of a cyclotomic integer by a rational integer.

A cyclotomic integer is divisible by a rational integer if and only if all of its integer coefficients are congruent modulo the rational integer.

Proof:

(1) Let f(α) be a cyclotomic integer.

(2) f(α) = a₀ + a₁α + ... a_λ-1α^λ-1 [See Lemma 1 here for details]

(3) Let d be a rational integer.

(4) It is clear that if d divides f(α), then a₀ ≡ a₁ ≡ ... ≡ a_λ-1 ≡ 0 (mod d).

(5) Assume a₀ ≡ a₁ ≡ ... ≡ a_λ-1 (mod d).

(6) Then, using Corrolary 2.1 from here, we know that we can add a_λ-1 to each of the coefficients to get:

f(α) = (a₀ - a_λ-1) + (a₁ - a_λ-1)α + ... + (a_{λ - 2} - a_{λ - 1})α^λ-2 + (a_λ-1 - a_λ-1)α^λ-1

(7) But then it is clear that d divides each of the coefficients so it divides f(α).

QED

Corollary 1.1: Division Algorithm for a cyclotomic integer f(α) by a rational integer d

if f(α) = a₀ + a₁α + ... + a_λ-1α^λ-1, the result is:

[(a₀ - a_λ-1)/d] + [(a₁ - a_λ-1)/d]α + ... + [(a_λ-2 - a_λ-1)/d]α^λ-2

Proof:

(1) If d divides f(α), then a₀ ≡ a₁ ≡ ... ≡ a_λ-1 (mod d) [From Lemma 1 above]

(2) By Corollary 2.1 here, we can add constant -c to each coefficient and still maintain the same value so that:

f(α) (a₀ - a_λ-1) + (a₁ - a_λ-1)α + ... + (a_{λ - 2} - a_{λ - 1})α^λ-2 + (a_λ-1 - a_λ-1)α^λ-1

(3) From this we know that d divides each coefficient and the result of this corrollary follows.

QED

Lemma 2: Division Algorithm for Cyclotomic Integers

A cyclotomic integer h(α) is divisible by another cyclotomic integer f(α) if and only if:

h(α)*f(α)^-1 is divisible by the Nf(α)


(1) Let f(α),h(α) be cyclotomic integers.

(2) We can assume f(α) ≠ 0

(a) Assume f(α) = 0.

(b) Then, g(α) exists only if h(α) = 0 in which case g(α) can take any value.

(c) This resolves f(α) = 0 so we only need to address the case where f(α) ≠ 0.

(3) Assume f(α) * g(α) = h(α)

(4) Then, Nf(α)*g(α) = h(α) *f(α²)*f(α³)*...*f(α^λ-1) = h(α)*f(α)^-1

(5) We see that f(α) divides h(α) if and only if Nf(α) divides h(α)*f(α³)*...*f(α^λ-1).

(6) But Nf(α) is a rational integer. [See Lemma 5 here]

(7) Let i(α) = h(α)*f(α)^-1

(8) i(α) = b₀ + b₁α + ... + b_λ-1α^λ-1

(9) Using Lemma 1 above, we see that Nf(α) divides i(α) if and only if for any two coefficients b_j ≡ b_k (mod Nf(α))

(10) But from step #5, we have that f(α) divides h(α) if and only if after computing i(α) from step #8, we find that all coeffients of i(α) are congruent modulo Nf(α).

QED

Corollary 2.1: Method for determining result of division between two cyclotomic integers.

if f(α) = a₀ + a₁α + ... + a_λ-1α^λ-1 and:

h(α)f(α)^-1 = b₀ + b₁α + ... + b_λ-1α^λ-1,

the result is:

[(b₀ - b_λ-1)/Nf(α)] + [(b₁ - b_λ-1)/Nf(α)]α + ... + [(b_λ-2 - b_λ-1)/Nf(α)]α^λ-2

Proof:

(1) Let f(α), g(α), h(α) be cyclotomic integers with h(α) = f(α)g(α).

(2) Multiplying both sides by f(α)^-1 gives us:

Nf(α)g(α) = h(α)f(α)^-1

(3) Since Nf(α) is a rational integer, we can apply Corollary 1.1 above to get the desired result.

QED