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

Tuesday, August 15, 2006

Ideal Numbers: Norm of an Ideal Number

In my last blog, I offered a definition of an ideal number. Based on this definition, it is possible to define a norm function that maps a divisor to a rational integer by multiplying it with its conjugates.

The norm of an ideal number is more than a curiosity. It has an interesting property. The norm for any ideal number is also the number of incongruent classes modulo that ideal number. I use this result in my proof of the existence of the class number for any set of cyclotomic integers. I go over this property of norms of ideal numbers here.

Today's content is once again based on Harold M. Edwards' Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.

Definition 1: Norm of an Ideal Number

For an ideal number A, the norm N(A) = A*σA*σ2A*...*σλ-2A.

For details on what σA means please see the Definition 1, here.

Lemma 1: N(AB)=N(A)*N(B)

Proof:

N(AB) = AB*σ(AB)*σ2(AB)*...*σλ-2(AB) =

= A*B*σA*σB*σ2(A)*σ2(B)*...*σλ-2(A)*σλ-2(B) =

= A*σA*σ2(A)*...*σλ-2(A)*B*σB*...*σλ-2B =

= N(A)*N(B)

QED

Lemma 2: if p ≠ λ, then P*σP*σ2P*...*σe-1P = p

NOTE: e = (λ - 1)/f where f = exponent mod λ for p. [See Definition 2, here]

Proof:

(1) Let P be a prime divisor that divides a rational integer p.

(2) From a previous result (see Lemma 1, here), we know that P, σP, σ2P, ..., σe-1P are the e distinct divisors that divide p.

(3) We know that if any cyclotomic integer g(α) is divisible by all the prime divisors of p, then it is also divisible by p. Likewise, we know that if g(α) is divisible by p, then it is divisible by all the prime divisors. (See Theorem, here)

(4) In other words, the product of all prime divisors is principal and it is equal to p.

QED

Lemma 3: For a Prime Divisor P that divides p, the N(P) is a rational integer.

Proof:

(1) If p = λ, then P = α - 1 and N(P) = λ [See Lemma 2, here]. So now, we can assume that p ≠ λ in order to complete the proof.

(2) If p ≠ λ, then N(P) = P*σP*σ2P*...*σλ-2P. [See Definition above]

(3) Since σ is a permutation and there are only e distinct prime divisors, we get the following:

N(P) = (P*σP*σ2P*...*σe-1P)*(P*σP*σ2P*...*σe-1P)*...*(P*σP*σ2P*...*σe-1P)

(4) Applying Lemma 2 above gives us:

N(P) = p*p*...*p = pf [since ef = λ - 1, from the definition of exponent mod λ, see Definition 2, here]

QED

Lemma 4: For any ideal number A, the N(A) is a rational integer.

Proof:

(1) Every ideal number A is composed of powers of prime divisors. [See here for definition of ideal number]

(2) Let us assume that the powers of prime divisors of A consist of: P1a*P2b*...*Pnc

(3) Then using Lemma 1 above, N(A) = N(P1a*P2b*...*Pnc) =

= N(P1a)*N(P2b)*...*N(Pnc) =

= N(P1)*...*N(P1)*N(P2)*...*N(P2)*...*N(Pn)*...*N(Pn)

(4) Using Lemma 3 above, we know that each N(Pi) is a rational integer. This then gives us our result since the product of a set of rational integers is itself a rational integer.

QED

Lemma 5: if g(α) is a cyclotomic prime that divides p where p ≠ λ and P is the divisor for g(α), then p divides g(α)*σg(α)*σ2g(α)*...*σe-1g(α) with a multiplicity of 1.

Proof:

(1) If a prime divisor P is the divisor for g(α), then p divides g(α)*ψ(η) [See Definition 7, here for definition of divisible by a prime divisor]

(2) This means that σp divides σ(g(α)*ψ(η)) and since p is a rational integer σ p = p and we have p divides σg(α)*σψ(η)

(3) Using the definition for divisibility of a prime divisor, we see that σP divides σg(α).

(4) We can make the same argument to show that σ2P divides σ2g(α) and so on up until σe-1P divides σe-1g(α).

(5) This gives us that the rational prime p divides g(α)*σ(gα)*...*σe-1g(α). [See Theorem here, since division by all e of the prime divisors implies that p divides a given cyclotomic integer]

(6) Assume that p divides g(α)*σg(α)*...*σe-1g(α) with a multiplicity greater than 1.

(7) Then the prime divisor P which divides p exactly once (from the theorem mentioned in step #5) would have to divide g(α)*σg(α)*...*σe-1g(α) with the same multiplicity.

(8) But since P is the divisor of g(α), this would imply that g(α) must divide g(α)*σg(α)*...*σe-1g(α) with a multiplicity greater than one which is not the case.

(9) So we reject the assumption in step #6 and conclude that p divides g(α)*σg(α)*...*σe-1g(α) exactly once.

QED

Lemma 6: If a prime divisor P for a prime p ≠ λ is principal such that it is the divisor of a cyclotomic prime g(α), then N(P) = Ng(α)

Proof:

(1) From Lemma 3 above, N(P) = pf

(2) By definition of a divisor, we know that g(α) divides p [since P divides p and P is the divisor of g(α)]

(3) Ng(α) = g(α)*g(α2)*...*g(αλ-1) [See definition of norm for cyclotomic integers]

(4) Np = pλ-1 [See definition of norm for cyclotomic integers]

(5) We know that Ng(α) must be equal to a power of p since:

(a) N(p) = pλ-1 [See definition of norm for cyclotomic integers]

(b) Ng(α) divides N(p) since g(α) divides p [See Lemma 6, here]

(6) Ng(α) ≡ g(1)λ-1 ≡ 0 or 1 (mod α - 1) since:

(a) α ≡ 1 (mod α -1)

(b) Ng(α) = g(α)*g(α2)*...*g(αλ-1,) [Definition of Ng(α), see here]

(c) Using step #6a, we have:

g(α)*g(α2)*...*g(αλ-1,) ≡ g(1)*g(1)*...*g(1) = g(1)λ-1 = (a0 + a1 + ... + aλ-1)λ-1 = rational integer r (since ai are all rational integers).

(d) Now, since N(α - 1) = (α - 1)(α2 - 1)*...*(αλ-1-1) = λ (see Lemma 2, here), we know that (α-1) divides λ.

(e) Since λ is a prime, we know that either λ divides r or it does not. If it does, then g(1)λ-1 ≡ 0 (mod α -1 ).

(f) If λ does not divide g(1)λ-1, then gcd(λ,g(1)λ-1) = 1 [Since λ is a prime]

(g) Using Bezout's Identity, there exists a,b such that a*λ + b*g(1)λ-1 = 1.

(h) This gives us that b*g(1)λ-1 - 1 = (-1)(aλ) so that b*g(1)λ-1 ≡ 1 (mod λ).

(7) So, from step #6, we see that g(1)λ-1 ≡ 0 or 1 (mod α - 1) if and only if g(1)λ - 1 ≡ 0 or 1 (mod λ)

(8) We know that λ does not divide Ng(α) since Ng(α) = px (from step #5 above) and since gcd(p,λ)=1.

(9) So, we are left with Ng(α) ≡ 1 (mod λ) which means that if Ng(α) = px then x is divisible by f where f is the exponent mod λ for p. [See Lemma 1, here]

(10) Finally, we show that Ng(α) = pf since:

(a) We can divide up Ng(α) into [g(α)*σg(α)*...*σe-1g(α)]*[σeg(α)* σe+1g(α)*...*σ2e-1g(α)]*...*[σ(f-1)*eg(α)σ(f-1)*e+1g(α)*...*σ(f-1)*e+e-1g(α)]

(b) By the reasoning in Lemma 5 above, each of these f groupings of e elements is divisible by at most once by p. So that all f of these groups is divisible at most by pf.

(c) Thus, it follows that if Ng(α) = pa, then a = f.

QED


Lemma 7: Criteria for a Principal Divisor

An ideal number A is a principal divisor for a cyclotomic integer g(α) if for any prime divisor Pn:

Pn divides A if and only if Pn divides g(α)

Proof:

(1) An ideal number by definition is a set of powers of prime divisors. [See Definition 3, here]

(2) So, if each power of each prime that makes up an ideal number A divide a given cyclotomic integer g(α), then A divides g(α)

(3) This gives us that if g(α) divides a second cyclotomic integer h(α), then A also divides h(α).

(4) Now, to complete this proof, we need to show that if A divides h(α), then g(α) also divides h(α).

(5) By the given, we know that A represents a complete set of prime divisors that divide g(α).

We know this since if there is any prime divisor Pn that does not divide A, then it does not divide g(α).

(6) So, applying the Fundamental Theorem for Ideal Numbers, we know that if A divides a second cyclotomic integer h(α), then g(α) also divides h(α).

QED

Lemma 8: If an ideal number A is the principal divisor for a cyclotomic integer g(α), then σA is the principal divisor for a σg(α)

Proof:

(1) This lemma is established if we can use the criteria in Lemma 7. That is, we want to show that for any prime divisor Pn:

Pn divides σA if and only if Pn divides σg(α).

(2) Assume Pn divides σA

(3) Then σ-1Pn divides A.

(4) And σ-1Pn divides g(α) since A is the principal divisor for g(α).

(5) And Pn divides σg(α).

(6) Assume Pn divides σg(α)

(7) Then σ-1Pn divides g(α) so σ-1Pn divides A [Since, A is the principal divisor for g(α).]

(8) Which gives us that Pn divides σA.

QED

Theorem: If an ideal number A is the principal divisor for a cyclotomic integer g(α), then N(A) is the principal divisor for Ng(α)

Proof:

(1) This lemma is established if we can use the criteria in Lemma 7. That is, we want to show that for any prime divisor Pn:

Pn divides N(A) if and only if Pn divides Ng(α).

(2) Assume Pn divides N(A)

(3) N(A) = A*σA*σ2A*...*σλ-2A

(4) From our assumption in step #2, we know that: Pn divides a subset of the list of ideal numbers in step #3 so that we have:

Pn divides σaA*...*σcA.

(5) Since g(α) = g(α)*σg(α)*...*σλ-2g(α), we can apply Lemma 8 above to conclude that:

σaA is the principal divisor for σag(α)
...
σcA is the principal divisor for σcg(α)

(6) Finally, this gives us that Pn divides Ng(α) since each Pi that divides a given σiA also must divide the given σig(α) and therefore divide Ng(α).

(7) Assume Pn divides Ng(α)

(8) Again Pn can only divide Ng(α), if its divides between 1 and n cyclotomic integers of the form σig(α).

(9) It would then divide each of the principal divisors σiA for those cyclotomic integers and thereby divides N(A).

QED

Corollary: If an ideal number A is the principal divisor for a cyclotomic integer g(α), then N(A) = Ng(α)

Proof:

(1) N(A) is a rational integer (See Lemma 4 above) and Ng(α) is a rational integer (see Lemma 5, here)

(2) Since every prime divisor Pn that divides N(A) also divides Ng(α) [By the Theorem above], we know that N(A) ≤ Ng(α).

(3) Since every prime divisor Pn that divides Ng(α) also divides N(A), we know that Ng(α) ≤ N(A).

(4) The conclusion follows.

QED

Ideal Numbers: Ideal Number Defined

In a previous blog, I spoke a good deal about ideal numbers but I avoided defining them. Instead, I've defined congruence modulo an ideal number and divisible by an ideal number. But, what exactly is an ideal number in and of itself? This is what I will define in today's blog.

Most of the content in today's blog is taken from Harold M. Edwards Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.

Edwards argues that "ideal number" is a misleading term because it begs the question "what is an ideal number." He prefers the term "divisor." Throughout my blog, I will use both terms.

In order to define ideal numbers, I will need to use the following thereom:

Theorem 1: There exists a cyclotomic integer φ(η) such that φ(η) is divisible exactly once by a given prime divisor P that divides a prime p but is not divisible by any other prime divisor of p.

Proof:

(1) We can assume that p ≠ λ since it p = λ this theorem is clearly met with α - 1 as the cyclotomic integer.

(2) Let ψ(η) be the formula constructed as before from η1, ..., ηe and u1, ..., ue where e = (λ - 1)/f where f is the exponent mod λ for p. [See here for definition of exponent mod λ]

(3) As was shown before, ψ(η) is divisible by all but one of the e prime divisors of p.

(4) Let φ(η) = σψ(η) + σ2ψ(η) + ... + σe-1ψ(η).

(5) φ(η) is now divisible only by one prime divisor of p (the one that didn't divide ψ(η) and is not divisible by any of the other prime divisors.

We know this is true in since in each case, all but one of the values is divisible by a prime divisor of p. So, if it divides all but the first element that result is:

nonzero + 0 + 0 + ... + 0 ≡ nonzero (mod a prime divisor of p)

On the other hand for the prime divisor that doesn't divide ψ(η), we know that all elements of the summation are divisible by this prime divisor.

NOTE: The reason this is true is that the σ function shifts the ηi value. So while uj - ηi is included in ψ(η), when we apply σ to it, we get uj - ηj. In other words, since we are including all possible shifts as part of the sum, one of these shifts results in a difference which is divisible by p.

(6) If φ(η) is divisible exactly once by the given prime divisor of p, then φ(η) has the required properties and we are done.

(7) If φ(η) is divisible more than once, then φ(η) + p has the property that we are looking for.

(a) Only one of the prime divisors of p divides φ(η) + p

Since each of the prime divisors of p divides p (see Theorem, here), we know that all but one cannot divide φ(η) + p [If any other prime divisors divides φ(η) + p, then it would also divide φ(η) since it divides p. But this is not the case as shown in step #4]

(b) It is only divisible once by the prime divisor of p in question

This is true because the prime divisor of p only divides p once [Since there are e distinct prime divisors that divide up p, see Lemma 1, here]

If the prime divisor of p divides φ(η) + p more than once, then it would divide p more than once (since it divides φ(η) more than once) which it does not.

QED

Definition 1: Prime Divisor P of p

A prime divisor P that divides a rational prime p is defined as gcd(p,φ(η)) where φ(η) is the cyclotomic integer that satisfies the theorem above.

Observation:

A prime divisor is the greatest common denominator between p and the cyclotomic integer φ(η). It may or may not correspond to a real cyclotomic prime. When it corresponds to a cyclotomic prime, we say that the prime divisor is principal (see here for more on principal ideal numbers).

In my next blog, I will talk about the norm of ideal numbers. To do this, I will need to define a version of the σ permutation for ideal numbers.

Definition 2: σP

σP = σ(p,ψ(η)) = (p,σψ(η))

Observation:

We can see that the σ transformation changes a given prime divisor P1 of p into another prime divisor, say, P2 of p.

Definition 3: ideal number

An ideal number is the product of powers of prime divisors .

Observation:

We can see that just like a prime divisor, an ideal number may correspond to a real cyclotomic integer or it may not. When it corresponds to a real cyclotomic integer, we say that the ideal number is principal.

Definition 4: σ for ideal numbers

For an ideal number A:

σA = σ(P
1a*P2b*...*Pnc) = σ(P1a)*σ(P2b)*...*σ(Pnc) =

= (σP1)a*(σP2)b*...*(σPnc)