Friday, August 04, 2006

Ideal Numbers: Additive Group of Cyclotomic Integers Mod p

In today's blog, I will introduce the idea of Additive Groups and talk specifically about the Additive Group of Cyclotomic Integers Mod p where p is an prime integer that is distinct from λ.

Additive groups are important because it enables us to use Lagrange's Theorem on the subgroup.

Definition 1: Additive group

An additive group is a group defined around the operation of addition. [See here for a review of the concept of a group]

Example: Z9 is an additive group

Z9 = { 0, 1, 2, 3, 4, 5, 6, 7, 8 }

It is clear that it has all the properties of a group:

(1) Closure: addition of any two integers modulo 9 results in another integer modulo 9.

(2) Identity: 0 is the identity.

(3) Inverse: For any integer, 9-i is the inverse. For example, 1 + 8 = 0 modulo 9.

(4) Associativity: For any a,b,c ∈ Z9, we see that:

a + (b + c) = (a + b) + c

In talking about the additive group of cyclotomic integers mod p, it is useful to talk about the number of elements.

Lemma 1: The additive group of cyclotomic integers mod p has pλ-1 elements.

Proof:

(1) Let λ be an odd prime and let α be a root of unity such that αλ = 1 but for all positive integers i less than λ, αi ≠ 1. [See here for review of roots of unity]

(2) All cyclotomic integers based on λ can be put into this form:

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

where ai are all integers [See Lemma 1 here]

(3) Since we are talking about values modulo p, we can assume that ai is between 0 and p-1.

(4) This means that there are λ-1 elements that can take values of 0 to p-1.

(5) If we count all possible values, this leads us to λ - 1 multiples:

[0..p-1]*[0..p-1]*...*[0..p-1] = pλ-1

QED

The importance of this is that we can construct an additive group of cyclotomic integers using a congruence relation ~ where p ~ 0. In other words, we can use ψ(η)p (see definition here) to define the following congruence relation:

f(α) ~ g(α) if and only if f(α)ψ(η)p ≡ g(α) mod p.

From this perspective, the congruence relation ~ can be used to construct a set of additive group of cyclotomic integers which consists of each distinct classes of f(α)ψ(η)p (mod p).

Lemma 2: if ~ is a congruence relation such that p ~ 0, then the additive group of cyclotomic integers created from ~ is a subgroup of the additive group of cyclotomic integers mod p.

Proof:

(1) We know that the set of cyclotomic integers mod p under '+' is an abelian group since:

(a) It is closed on the operation of '+'

(b) 0 mod p is the identity element.

(c) For any cyclotomic integer ≡ r (mod p), the inverse element is p-r.

(d) '+' is clearly associative in nature.

(e) It is abelian since '+' is commutative.

(2) We can make the same arguments to show that the cyclotomic integers from ~ is an abelian group on the operation of addition.

(3) To complete this proof, we only need to show that the set of cyclotomic integers ~ is a subset of the cyclotomic integers mod p.

(4) This is the case since:

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

(b) Then, there exists r(α) such that g(α) ~ r(α) so that r(α) ∈ additive group of cyclotomic integers constructed through ~

(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' because p ~ 0.

(e) But if all ai are between 0 and p-1, then r(α) ∈ the additive group of cyclotomic integers mod p.

QED

No comments: