## Saturday, August 05, 2006

### Ideal Numbers: Prime Cyclotomic Integers

The beauty of Ernst Kummer's prime divisors is that they have the same "action" as the real cyclotomic primes when they exist.

In today's blog, I will demonstrate the very important point that when cyclotomic integers exist, they behave in exactly the same way as the prime divisors. Now, interestingly, this point is not needed to establish ideal numbers.

In fact, even if prime divisors behaved differently, as long as they behaved consistently, that would be enough. Still, it is a tribute to Kummer and a tribute to his ideas that prime divisors are a generalization of the prime cyclotomic integers rather than a replacement.

In today's blog, I assume that you are familiar with "prime divisors" of ideal numbers. If you are not, please start here.

Definition 1: A prime congruence relation

A congruence relation ~ is said to be "prime" if ab ~ 0 implies a ~ 0 or b ~ 0.

It should be clear that this definition applies to standard primes since by Euclid's Lemma a prime p divides ab implies p divides a or p divides b.

For the first lemma, I use the concept of the exponent mod λ for p. If you are not famliar with this idea, see Definition 2, here.

Lemma 1: Maximum congruence classes

If ~ is a congruence relation on cyclotomic integers with αλ = 1 with all the usual properties (it is reflexive, symmetric, transitive, and consistent with addition and multiplication) in which ηi is congruent to ui, p is congruent to 0, and 1 is not congruent to 0, then there is a maximum of pf congruence classes where f is the exponent mod λ for p.

Proof:

(1) Let ~ be a congruence relation that has all the properties of the given.

(2) Since every cyclotomic integer g(α) can be written in the form g1(η)αf-1 + g2(η)αf-2 + ... + gf(η) [See Lemma 1, here], it follows that g(α) ~ a1αf-1 + a2αf-2 + ... + af where 0 ≤ ai ≤ p-1. [Since the assumption is p ~ 0] as well as g(α) ≡ a1αf-1 + a2αf-2 + ... + af where 0 ≤ ai ≤ p-1

(3) Therefore, there are at most pf incongruent cyclotomic integers modulo the congruence relation. [From step #7, see Corollary 2.1, here]

QED

Lemma 2: Prime Congruence Relation

If ~ is a congruence relation on cyclotomic integers with αλ = 1 with all the usual properties (it is reflexive, symmetric, transitive, and consistent with addition and multiplication) in which ηi is congruent to ui, p is congruent to 0, and 1 is not congruent to 0, then we can assume it is prime.

Proof:

(1) Let ~ be a congruence relation that has all the properties of the given.

(2) Using Lemma 1 above, we know that there are at most pf incongruent cyclotomic integers modulo the congruence relation. [From step #7, see Corollary 2.1, here]

(3) Assume that ~ is not prime.

(4) This means that there exists a(α), b(α) such that a(α)b(α) ~ 0 but a(α) not ~ 0 and b(α) not ~ 0. [See Definition 1 above]

(5) We can define another congruence relation ~2 such that:

g(α) ~2 φ(α) if and only if g(α)a(α) ~ φ(α)a(α)

(6) We can see that ~2 is reflexive, symmetric, transitive, and consistent with addition and multiplication with ηi ~2 ui, p ~2 0, and 1 not ~2 0. [Since by the given ~ has these properties and multiplying each side of a congruence by a(α) will still maintain the properties]

(7) We can also see that this relation has fewer incongruent integers from ~ since:

b(α) ~2 0 but b(α) not ~ 0 (by step #3 above since b(α) ~2 a(α)b(α) ~2 0)

(8) So ~2, we see has pf-1 incongruent cyclotomic integers; that is, it has at least 1 less than ~.

This is the case since we are effectively removing b(α) as a distinct congruence class. Since a(α)b(α) ~ 0 by assumption in step #4, b(α) ~2 0 since b(α) ~2 0 if and only if b(α)a(α) ~ 0.

(9) Now, if ~2 is not prime, then we repeat the steps #5 thru #9, to derive a congruence relation ~3 with at most pf-2 incongruent cyclotomic integers. We can keep on repeating this until finally we reach a situation where we have a congruence relation ~n that has all the properties of ~ and which is in addition prime. For example, we know that eventually, we have only {0,1} left which is prime.

Since we can repeat #6 each time we find a situation which is not prime. We know that {0,1} is prime since there are only 4 combinations:
0*0 ~ 0
0*1 ~ 0
1*0 ~ 0
1*1 ~ 1

In all cases ab ~ 0 if and only if a ~ 0 or b ~ 0.

(10) So, we can assume that there exists a congruent relation ~n with all the properties of ~ which is prime.

QED

Before starting on Lemma 3, if you are not familiar with the additive group of cyclotomic integers mod p, then it is recommended, that you review here first.

Lemma 3: Minimum number of congruence classes

If ~ is a congruence relation on cyclotomic integers with αλ = 1 with all the usual properties (it is reflexive, symmetric, transitive, and consistent with addition and multiplication) in which ηi is congruent to ui, p is congruent to 0, and 1 is not congruent to 0, then there are a minimum of pf congruence classes where f is the exponent mod λ for p.

Proof:

(1) We know from Lemma 1 above, that there are a maximum of pf congruence classes where f is the exponent mod λ for p.

(2) By Lemma 2 above, we can assume that ~ is prime.

(3) Now, we can also see that set of cyclotomic integers that make up the congruence relation ~ is a subgroup to the additive group of cyclotomic integers mod p since:

(a) Let g(α) be a cyclotomic integer.

(b) Then, there exists r(α) such that g(α) ~ r(α)

(c) Now we can assume r(α) has the following form (see Lemma 1, here):

a0 + a1α + ... + aλ-1αλ-1

(d) We can further assume that all ai are between 0 and p-1 since if ai is greater than p, then there exists a' such that ai ≡ a' (mod p) where a' is less than p and further if ai ≡ a' (mod p), then aiψ(η) ≡ a'ψ(η) (mod p).

(e) But if all ai are between 0 and p-1, then r(α) ∈ the additive group of cyclotomic integers mod p. [See Lemma 2, here for details.]

(4) So, using Lagrange's Theorem, we see that the number of incongruent cyclotomic integers must divide the number of cyclotomic integers mod p; so it it is a power of p.

(5) the number of incongruent cyclotomic integers is greater than 1 (because 1 not ~ 0 so there is at least two)

(6) the number of incongruent cyclotomic integers is congruent to 1 mod λ since:

The subsets of the form g(α), g(α)α, g(α)α2, ..., g(α)αλ are nonoverlapping sets containing exactly λ incomplete nonzero cyclotomic integers so we get mλ nonzero cyclotomic integers + 1 zero cyclotomic integer = mλ + 1.

(7) Therefore, it is a positive power of p and must be at least pf since:

We have shown that the number of incongruent integers must be a power of p (step #18), p ≥ 1 (step #19) and must be ≡ 1 (mod λ) (by step #20) so that we have:

px ≡ 1 (mod λ)

From the given, the lowest positive integer that this can be is f. [See definition 2, here]

QED

Lemma 4: Unique Congruence Relation

It is possible to define one and only one congruence relation on cyclotomic integers with αλ = 1 with all the usual properties (it is reflexive, symmetric, transitive, and consistent with addition and multiplication) in which ηi is congruent to ui, p is congruent to 0, and 1 is not congruent to 0.

Proof:

(1) Let be a congruence relation such that αλ = 1 with all the usual properties (it is reflexive, symmetric, transitive, and consistent with addition and multiplication) in which ηi is congruent to ui, p is congruent to 0, and 1 is not congruent to 0.

(2) Let ~ denote any other congruence relation that is reflexive, symmetric, transitive, and consistent with addition and multiplication where ηi ~ ui, p ~ 0, and 1 not ~ 0.

(3) From definition 4 here, we can construct the following:

ψ(η)p: a product of ep - e factors j - ηi with j ≠ ui is not divisible by p.

There exist u1, u2, ... , ue with the property that every equation satisfied by the periods η of length f is satisfied as a congruence modulo p by the integers u. [See Corollary 3.1, here]

(4) From this, it will be shown that ~ is completely determined, because for any given g(α) and φ(α), one can find g(α) ~ a1αf-1 + a2αf-2 + ... + af and φ(α) ~ b1αf-1 + b2αf-2 + ... + bf where ai, bi are the integers 0 ≤ ai ≤ p-1 and 0 ≤ bi ≤ p-1. [See step #7 if more details are needed]

(5) By the transitivity of ~ and the fact that ~ has pf incongruent cyclotomic integers, g(α) ~ φ(α) if and only if the cyclotomic integers a1αf-1 + a2αf-2 + ... + af and b1αf-1 + b2αf-2 + ... + bf are equal.

(6) Since has all the properties assumed for ~ it follows that coincides with ~.

QED

The main theorem of this section states the the concept of "prime divisors" is a generalization of prime cyclotomic integers. Technically, prime divisors are never defined. Rather, I have defined congruence modulo a prime divisor (see Definition 6, here). This is the reason for the wording of the theorem.

Theorem: The "congruence modulo prime divisors" coincides with congruence modulo cyclotomic primes whenever cyclotomic primes exist.

(1) For each cyclotomic prime g(α), there exists a standard prime p such that g(α) divides p. [See Lemma 1, here]

(2) We know that the only cyclotomic prime that divides λ is α - 1 which is a cyclotomic prime (see here) so for purposes of this proof, we can assume that p ≠ λ

(3) Let ~ be the congruence relation modulo g(α)

(4) We can see that ~ has the following properties:

(a) ~ is reflexive, symmetric, and transitive. [See here for definition of cyclotomic primes]

(b) ~ is consistent with addition and multiplication [See here for definition of cyclotomic primes]

(c) ηi ~ ui [This follows from Corollary 3.1, here since g(α) divides p]

(d) p ~ 0 [Since g(α) divides p]

(e) 1 not ~ 0 [This is clear since a prime does not divide 1 but does divide 0, see here for definition of a cyclotomic primes]

(5) So, this theorem is proved if we can show that there exists a congruence relation modulo a prime divisor P such that the congruence modulo P coincides with the congruence relation ~.

(6) Let ~2 be the congruence relation modulo a prime divisor P defined here.

(7) Now, we can also show that the congruence modulo P has the following properties:

(a) ~2 is reflexive, symmetric, and transitive. [this follows from the definition of ~2, see Definition 6, here]

(b) ~2 is consistent with addition and multiplication [this follows from the definition of ~2, see Definition 6, here]

(c) ηi ~2 ui [This follows from Corollary 3.1, here since p ~2 0]

(d) p ~2 0 [This follows from the definition of ~2, see Definition 6, here]

(e) 1 not ~2 0 [This follows from the definition of ~2 since (1)ψ(η)p not ~2 (0)ψ(η)p (mod p)]

(8) Using Lemma 4 above, we can conclude that ~ and ~2 are the same so we are done.

QED