Friday, August 18, 2006

Ideal Numbers: Distinct Congruence Classes Modulo an Ideal Number

Today's blog continues the proof for the existence of a class number for any set of cyclotomic integers. There is one last proof we need to complete this proof. We need to show that given a large enough set of cyclotomic integers with distinct congruence classes modulo an ideal number, that we can be certain that at least one is divisible by the ideal number. In other words, we can be sure that there exists within that the set of cyclotomic integers one that is congruent to 0 modulo the ideal number.

The answer to this question turns out to be the norm of the ideal number. For example, if we want to make sure that for a set of cyclotomic integers, a given ideal number A divides at least one, we can be sure of this if we have a set of N(A) distinct congruence classes.

The result presented in today's blog is taken 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 pf 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*σ2A*...*σλ-2A = (A*σA*σ2A*..*σ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) = pf.

(7) Using a previous result (see Theorem 3, here), we know that there are pf 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 = Pn 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 a0 + a1ψ(α) + a2ψ(α)2 + ... + an-1ψ(α)n-1 mod Pn and two cyclotomic integers of this form are congruent if and only if the coefficients a0, a1, ..., an-1 are the same mod P since:

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

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

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

(d) Let y(α) = x(α) - a0 - a1ψ(α) - ... - an-2ψ(α)n-2.

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

(f) Now, we need to prove that y(α) ≡ aψ(α)n-1 mod Pn 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 ≡ apn-1kn-1 (mod Pn)

(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 mn-1 to both sides of (h) gives us:

y(α)γ(α)n-1mn-1 ≡ apn-1kn-1mn-1 ≡ apn-1 (mod Pn)

(k) Since y(α) ≡ 0 (mod Pn-1) by assumption, then y(α)γ(α)mn-1 is divisible by pn-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 = Pn.

(4) This proves that the number of classes mod Pn is equal to the number of ways of choosing a0, a1, ..., an-1 mod P which is N(P)n = N(Pn).

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

1 comment:

Chris Austin said...

I found this page and your blog via a Google search for "modulo an ideal". It's been very helpful. Thanks.
Chris.