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