Thursday, June 01, 2006

Cyclotomic Integers: Divisibility Test

In today's blog, I continue to review results from Harold Edward's Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory. I am continuing down the same chapter that I started in an earlier blog. If you would like to start at the beginning of cyclotomic integer properties, start here.

Lemma 1: For every cyclotomic prime h(α), there exists a rational prime p such that h(α) divides p.

Proof:

(1) Let h(α) be a cyclotomic prime. [See here for a review of cyclotomic primes]

(2) We know that Nh(α) is a rational integer. [See Lemma 5, here]

(3) By the Fundamental Theorem of Arithmetic, Nh(α) consists of a set of rational primes: p1*...*pn.

(4) Since h(α) is a cyclotomic prime, it must divide one of these primes pi. [See Definition 4, here]

QED

Lemma 2: Every cyclotomic integer g(α) is congruent mod h(α) to a cyclotomic integer of the form a1αf-1 + a2αf-2 + ... + af where ai are positive integers less than a prime integer p.

Proof:

(1) From a previous result, we know that every cyclotomic integer g(α) can be expressed in the following form:

g(α) = g1(η)αf-1 + g2(η)αf-2 + ... + gf(η)

where gi(η) are cyclotomic integers made up of periods of length f. [See Corollary 3.1, here]

(2) Each cyclotomic integer gi(η) is congruent mod h(α) to an integer gi(u) where gi(u) denotes the integer obtained by substituting u1 for η1, u2 for η2, etc. [See Corollary 2.1, here]

(3) We know that there exists a rational prime p such that h(α) divides p. [See Lemma 1 above]

(4) We can assume that gi(u) is between 0 and p-1 since:

(a) Assume that gi(u) ≥ p.

(b) There exists a value i such that gi(u) ≡ i (mod p) and i is between 0 and p-1.

(c) But then gi(u) ≡ i (mod h(α)) since h(α) divides p.

(d) So, we can conclude that gi(η) ≡ i (mod h(α))

(5) So that putting it all together, we have:

g(α) = g1(η)αf-1 + g2(η)αf-2 + ... + gf(η) ≡ g1(u)αf-1 + g2(u)αf-2 + ... + gf(u) ≡

≡ a
1αf-1 + a2αf-2 + ... + af (mod h(α))

where ai is between 0 and p-1.

QED

Corollary 2.1: Every cyclotomic integer g(α) is congruent mod h(α) to 1 of pf specific cyclotomic integers.

Proof:

(1) From Lemma 2 above, every integer g(α) satisfies the equation below:

g(α) ≡ a1αf-1 + a2αf-2 + ... + af (mod h(α)) where ai is between 0 and p-1.

(2) Now the conclusion follows from noting that each of the f different integers can take p different values which gives us: pf different values.

QED

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

Lemma 3: 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

Lemma 4: if h(α) is a cyclotomic prime that divides a rational prime p, then the additive group of cyclotomic integers mod h(α) 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 mod h(α) 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 mod h(α) 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(α) (mod h(α)) so that r(α) ∈ additive group of cyclotomic integers mod h(α)

(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 h(α)) because h(α) divides p.

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

QED

Definition 2: Exponent of p mod λ

The exponent of p mod λ is the smallest positive integer whereby pf ≡ 1 (mod λ)

Lemma 5: Let S be the set of cyclotomic integers of the form a1αf-1 + a2αf-2 + ... + af where ai are positive integers less than p.

Two elements of S are congruent if and only if they are identical.

Proof:

(1) The number of incongruent elements mod h(α) is a power of p, say pn since:

(a) The additive group of cyclotomic integers mod h(α) is a subgroup of the additive group of cyclotomic integers mod p. [See Lemma 4 above]

(b) The additive group of cyclotomic integers mod p has pλ-1 elements. [See Lemma 3 above]

(c) Since the additive group of cyclotomic integers mod h(α) is a subgroup of the additive group of cyclotomic integers mod p, the order of the first group must divide pλ - 1. [By Lagrange's Theorem, see here]

(d) Because p is prime, the number of elements in the additive group of cyclotomic integers mod h(α) must be a power of p.

(2) The number of incongruent cyclotomic integers mod h(α) is at least λ + 1 because 0, α, α2, ..., αλ=1 are all incongruent mod h(α) since:

(a) Any cyclotomic integer divisible by h(α) must have a norm divisible by p [since p = Nh(α), see Lemma 6 here, and since h(α) divides g(α) → Nh(α) divides Ng(α), see Lemma 6 here]

(b) On the other hand, monomials αj - 0 have norm = 1 [See Lemma 5, here]

(c) The binomials αi - αj (where i is not congruent to j mod λ) have a norm equal to N(α-1)=λ [See Lemma 6, here]

(d) Neither 1 nor λ is divisible by p, so none of these cyclotomic integers are divisible by h(α)

(3) The number of nonzero incongruent cyclotomic integers mod h(α) is divisible by λ since:

(a) If α, α2, ..., αλ =1 are all the nonzero cyclotomic integers mod h(α), then there are exactly λ of them.

(b) Assume that there exists a cyclotomic integer ψ(α) such that ψ(α) is not congruent to 0 mod h(α) and ψ(α) is not congruent to αj mod h(α) for j = 1,2, ..., λ.

(c) Then ψ(α)α, ψ(α)α2, ..., ψ(α)αλ = ψ(α) are all nonzero mod h(α) [because h(α) is prime] and distinct mod h(α) [because ψ(α)αj ≡ ψ(α)αk would imply αj ≡ αk) and distinct from α, α2, ..., αλ (because ψ(α)αj ≡ αi would imply ψ(α) ≡ αk)

(d) If this is all the all the possible nonzero cyclotomic integers congruent to h(α), then there are of them.

(e) Eventually, we run out of possibilities. Let us say that this happens after m such iterations of step (#3c).

(f) Then, there are distinct nonzero cyclotomic integers mod h(α)

(4) From step #1, we get that the total number of nonzero distinct cyclotomic integers mod h(α) is pn - 1.

(5) So putting #4 with #3, we get:

mλ = pn - 1.

(6) This gives us that:

pn ≡ 1 ( mod λ)

(7) Since f is the exponent of p mod λ, (see definition 2 above), we know that n ≥ f. [We know that f ≠ 0 since pn is greater than λ + 1. ]

(8) Thus, the number of pn of incongruent elements mod h(α) is at least pf.

QED

Corollary 5.1: To test for divisibility by h(α), it is not necessary to know h(α) but only the integers ui where i is between 1 and e and for which ηi ≡ ui (mod h(α)) for all i between 1 and e.

Proof:

(1) We know that a cyclotomic integer g(α) is divisible by h(α) if g(α) ≡ 0 (mod h(α))

(2) For any cyclotomic g(α), we know that it is congruent to a cyclotomic integer of the form a1αf-1 + a2αf-2 + ... + αf (mod h(α)) [See Lemma 2 above]

(3) We can now use Lemma 5 above to test for divisibility.

QED

Monday, May 29, 2006

Cyclotomic Integers: Generalizing Periods

In today's blog, I continue to review results from Harold Edward's Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory. I am continuing down the same chapter that I started in an earlier blog. If you would like to start at the beginning of cyclotomic integer properties, start here.

Lemma 1: Any arbitary cyclotomic integer g(α) of degree f-1 or less can be expressed in terms of cyclotomic integers made up of periods of length f such that:

g(α) = g1(η)αf-1 + g2(η)αf-2 + ... + gf(η)

where g1(η), g2(η), ..., gf(η) are cyclotomic integers made up of periods of length f. [See Definition 2 here for review of cyclotomic integers made up of periods of length f]

Proof:

(1) Let g(α) be a cyclotomic integer of degree f-1 so that:

g(α) = a0 + a1α + a2α2 + ... + af-1αf-1

(2) Let's define the following polynomials made up of periods of length f [letting e = (λ-1)/f]:

Let gf(η) = a0 + (0)η0 + (0)η1 + ... + (0)ηe-1

Let gf-1(η) = a1 + (0)η0 + (0)η1 + ... + (0)ηe-1

and so on until:

Let g1(η) = af-1 + (0)η0 + (0)η1 + ... + (0)ηe-1

(3) With the values in (step #2), we see that:

g(α) = g1(η)αf-1 + g2(η)αf-2 + ... + gf(η)

QED

Lemma 2: If g(α), h(α), and i(α) are cyclotomic integers expressible in terms of cyclotomic integers made up of periods of length f,

then g(α)h(α) + j(α) is expressible in terms of cyclotomic integers made up of periods of length f.


Proof:

(1) Since g(α), h(α), and j(α) are expressible in terms of cyclotomic integers made up of periods of length f, we have:

g(α) = g1(η)αf-1 + g2(η)αf-2 + ... + gf(η)

h(α) = h1(η)αf-1 + h2(η)αf-2 + ... + hf(η)

j(α) = j1(η)αf-1 + j2(η)αf-2 + ... + jf(η)

where where g1(η), g2(η), ..., gf(η), hi(η), ji(η) are cyclotomic integers made up of periods of length f.

(2) We know that the sum of two cyclotomic integers expressible in terms of cyclotomic integers made up of periods of length f is itself expressible in terms of cyclotomic integers made up of periods of length f.

If s(α) = g(α) + h(α) then we can define the following:

For each gi(η), hi(η), we have:

gi(η) = a0 + a1η0 + ... + afηf-1

hi(η) = b0 + b1η0 + ... + bfηf-1

And we can define si(η) such that:

si(η) = (a0 + b0) + (a1 + b10 + ... + (af + bff-1

(3) The product of g(α)*h(α) is also expressible in terms of cyclotomic integers made up of periods of length f since:

g(α)h(α) = [g1(η)αf-1 + g2(η)αf-2 + ... + gf(η)][h1(η)αf-1 + h2(η)αf-2 + ... + hf(η)] =

= [g1(η)αf-1][h1(η)αf-1] + ... + [ gf(η) ][hf(η)]

Since the product of two cyclotomic integers made up periods of length f is itself made up of periods of length f (see Corollary 4.1 here), we can conclude that the product of g(α)h(α) is itself a sum of cyclotomic integers made up of periods of length f.

Now from this sum and from the result in step #2, we are done.

QED

Lemma 3: There exists a function p(x) such that:

p(α) = αf + φ1(η)αf-1 + ... + φf-(η)α + φf(η) = 0

where φ1(η), φ2(η), ..., φf(η) are cyclotomic integers made up of periods of length f.

Proof:

(1) Let λ be an odd prime.

(2) Let α be a primitive root of unity such that λ is the least positive integer whereby αλ = 1.

(3) Let e,f be positive integers such that e is a factor of λ - 1 and f = (λ - 1)/e.

(4) Let p(x) be a function such that:



NOTE: In other words, p(x) = (x - σeα)(x - σ2eα)*...*(x - σfeα)

For review of σ notation, see here.

(5) If we multiply all of the products together, we get the following form:

p(x) = xf + φ1(η)xf-1 + ... + φf-(η)x + φf(η)

where φ(η) is a cyclotomic integer.

(6) We note that σep(x) = p(x) since:

(a) σep(x) = (x - σ2eα)(x - σ3eα)*...*(x - σefeα)

(b) σefe = σeσef = σeσλ-1 = σe [Since ef = λ - 1 by step #3 above and σλ-1 is identity from here]

(c) Combining (a) and (b) gives us:

σep(x) = (x - σ2eα)(x - σ3eα)*...*(x - σeα)

(7) From a previous result (see Lemma 4 here), we know that p(x) must consist of periods of length f so that taking our result from step #5:

p(x) = xf + φ1(η)xf-1 + ... + φf-(η)x + φf(η)

We know that φ1(η), φ2(η), ..., φf(η) must all be cyclotomic integers made up of periods of length f.

(8) Now we know that p(α) = 0 since:

(a) p(α) = (α - σeα)(α - σ2eα)*...*(α - σfeα)

(b) fe = λ - 1 (from step #3)

(c) σλ-1 is the identity (see here) so that σλ-1α = α

(d) Applying #8b and #8c to (a) gives us:

p(α) = (α - σeα)(α - σ2eα)*...*(α - σfeα) =

=(α - σeα)(α - σ2eα)*...*(α - α) =

= (α - σeα)(α - σ2eα)*...*(0) = 0

(9) So putting this all together gives us:

p(α) = αf + φ1(η)αf-1 + ... + φf-(η)α + φf(η) = 0

QED

Corollary 3.1: Every cyclotomic integer g(α) can be expressed in terms of cyclotomic integers made up of periods of length f such that:

g(α) = g1(η)αf-1 + g2(η)αf-2 + ... + gf(η)

where g1(η), g2(η), ..., gf(η) are cyclotomic integers made up of periods of length f.

Proof:

(1) Let g(α) be a cyclotomic integer such that:

g(α) = a0 + a1α + a2α2 + ... + aλ-1αλ-1

NOTE: See Lemma 1 here for details on why all cyclotomic integers can be expressed in this form.

(2) We can restate g(α) in terms of g(x) so that:

g(x) = a0 + a1x + a2x2 + ... + aλ-1

(3) Let p(x) be a polynomial such that:

p(x) = xf + φ1(η)xf-1 + ... + φf-1(η)x + φf(η)

where φ(η) is a cyclotomic integer.

(4) Using Division by Polynomials (see here) we know that there exists q(x),r(x) such that:

g(x) = q(x)(xf) + r(x) where degree of r(x) is less than f or r(x) = 0.

(5) Now from Lemma 1 above, we know that r(α) is expressible in terms of cyclotomic integers made up of periods of length f.

(6) Since p(α) = 0 (see Lemma 3 above), we know that αf is expressible in terms of cyclotomic integers made up of periods of length f since:

αf = 1(η)xf-1 - ... - φf-1(η)x - φf(η)

(7) For now, let's assume that q(x) is of degree less than f.

(8) Then we can apply Lemma 1 above and conclude that q(x) is expressible in terms of cyclotomic integers made up of periods of length f.

(9) Now since g(α) = q(α)(αf) + r(α), we can apply Lemma 2 above to conclude that g(α) is expressible in terms of cyclotomic integers made up of periods of length f.

(10) Now let's assume that q(α) is of degree f.

(11) Using q(x), we can again apply the Division Algorithm for Polynomials to get:

q(x) = q1(x)(xf) + r(x)

Since we are assuming q(x) has a degree of f, it follows that q1(x) will have a degree less than f.

(12) Using Lemma 2 above, we can conclude that q(α) is expressible in terms of cyclotomic integers since q1(α), αf, and r(α) are expressible in terms of cyclotomic integers made up of periods of length f.

(13) Using the Principle of Induction, we can now conclude that this works regardless of the degree of q(α). [Since q(α) with degree f-1 works and since q(α) with degree f-1 working implies that a q(α) with degree f works]

(14) So, using Lemma 2 above, since q(α), r(α), and αf are expressible in terms of cyclotomic integers made up of periods of length f, so is g(α) since:

g(α) = q(α)αf + r(α)

QED

Example:

Let λ = 5, f = 2, and γ = 2

So e = (λ - 1)/f = 4/2 = 2

Let g(α) = α4 + 2α3 + 3α2 + 4α + 5

We note that:

21 ≡ 2 (mod 5)
22 ≡ 4 (mod 5)
23 ≡ 3 (mod 5)
24 ≡ 1 (mod 5)

In this case,

p(x) = (x - σeα)(x - σ2eα)

Now σeα = αγ2 = α4

σ2eα = αγ4 = α

So,

p(x) = x2 - x(α4 + α) + α5 = x2 - x(α4 + α) + 1.

We see that p(α) = 0 since:

p(α) = α2 - α(α4 + α) + 1 = α2 - 1 + α2 + 1 = 0

So that:

α2 = α(α4 + α) - 1

Let g(x) = x4 + 2x3 + 3x2 + 4x+ 5

Now, let's express each of these terms in terms of cyclotomic integers made up of periods of length f=2:

with:
η0 = α4 + α

η1 = α3 + α2

0)2 = α3 + α2 + 2.

0)(η1) = η0 + η1

Using the Division Algorithm for polynomials, we see that:

g(x) = q(x)(x2) + r(x)

where:

q(x) = x2 + 2x + 3

r(x) = 4x + 5

x2 = x(α4 + α) - 1

and:

q(α) = [α(α
4 + α) - 1] + [2α + 3] = α(η0 + 2) + (2)

r(α) = 4α + 5 = α(4) + (5)

α2 = [α(α4 + α) - 1] = α(η0) + (-1)

Then

g(α) = q(α)α2 + r(α) =

= α202 + 2η0) + α(2η0) + α(-η0 - 2) -2 + α(4) + (5) =

= [α(η0) -1](3η1 + 2) + α(η0 +2) + (3) =

= α(4η0 + 3η1+ 4) + (-3η1 + 1)

So, let:

g1(η) = 4η0 + 3η1 + 4

g2(η) = -3η1 + 1

And finally, this gives us:

g(α) = g1(η)α + g2(η)