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
Saturday, August 05, 2006
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
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
Wednesday, August 02, 2006
Ideal Numbers: Cyclotomic primes that divide a prime p ≠ λ
In a previous blog, I spoke about the properties of α - 1 and I showed that α - 1 is the only cyclotomic prime that divides λ. In today's blog, I will talk about properties of cyclotomic primes that divide a standard prime p such that p ≠ λ.
The content of today's blog is based on Harold M. Edwards' Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.
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 and h(α) is a prime that divides 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) ≡
≡ a1α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: p*p*...*p = 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: For each cyclotomic prime h(α) that divides a standard prime p ≠ λ, there exists a set of pf incongruent classes mod h(α) where f is the exponent mod λ
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 2λ 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 mλ 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
The content of today's blog is based on Harold M. Edwards' Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.
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 and h(α) is a prime that divides 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) ≡
≡ a1α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: p*p*...*p = 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: For each cyclotomic prime h(α) that divides a standard prime p ≠ λ, there exists a set of pf incongruent classes mod h(α) where f is the exponent mod λ
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 2λ 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 mλ 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
Ideal Numbers: α - 1
From the perspective of ideal numbers, there are two types of prime divisors. Prime divisors that divide a prime integer p where p ≠ λ (see here for review of λ and its relation to cyclotomic integers) and the prime divisor of λ.
In today's blog, I will go into detail into the prime divisor of λ. The important idea here is that λ has only a single prime divisor α - 1 which is also a cyclotomic integer.
In today's blog, I will review some basic properties of α - 1. The content of today's blog is based on Harold M. Edwards' Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.
Lemma 1: if n is an odd prime, then
(x - α)(x - α2)*...*(x - αn-1) = xn-1 + xn-2 + ... + 1
Proof:
(1) From a previous result, we have:
xn - 1 = (x - 1)(x - α)(x - α2)*...*(x - αn-1)
(2) Now xn - 1 divided by x-1 = xn-1 + xn-2 + ... + x + 1 since:
(x-1)(xn-1 + xn-2 + ... + x + 1) =
= xn + xn-1 + xn-2 + .... + x2 + x -xn-1 - xn-2 - .... - x2 - x - 1 =
= xn - 1
(3) Putting #2 and #1 together gives us:
xn-1 + xn-2 + ... + x + 1 = (x - α)(x - α2) * ... * (x - αn-1)
QED
This second lemma uses the result of Lemma 1 to show that the Norm of α - 1 is λ. If you need a review of the norm of cyclotomic integers, see Section 4, here.
Lemma 2: N(α - 1) = λ
Proof:
(1) N(α - 1) = N(1 - α) since:
N(α - 1) = (α - 1)(α2 - 1)*...*(αλ-1 - 1)
N(1 - α) = (-1)λ-1[(α - 1)(α2 - 1)*..*(αλ-1 - 1)
Since λ is odd, λ-1 is even and (-1)λ-1 = 1
(2) N(1 - α) = (1 - α)(1 - α2)*...*(1 - αλ-1) [See here for definition of norm for cyclotomic integers]
(3) From Lemma 1 above:
(x - α)(x - α2)*...*(x - αλ-1) = xλ-1 + xλ-2 + ... + x + 1
(4) Setting x = 1 gives us:
(1 - α)(1 - α2)*...*(1 - αλ-1) = 1λ-1 + 1λ-2 + ... + 1 + 1 = λ
QED
Lemma 3: (αj - 1) = (α - 1)*unit
Proof:
(1) αj - 1= (α - 1)(αj-1 + αj-2 + ... + 1)
(2) Since ab=c → N(a)N(b)=N(c) (See Lemma 6, here), we know that:
N(αj - 1) = N(α-1) * N(αj-1 + αj-2 + ... + 1)
which gives us that:
N(αj-1 + αj-2 + ... + 1) = N(αj - 1)/N(α - 1)
(3) From Lemma 2 above, N(α-1) = λ
(4) We can also conclude from Lemma 2 above that N(αj-1) = λ since (αj-1) is a conjugate of (α - 1).
(5) Therefore, N(αj-1 + αj-2 + ... + 1) = 1 which makes (αj-1 + αj-2 + ... + 1) a unit (see Definition 1, here)
QED
Corollary 3.1: (α -1 ) is the only cyclotomic prime that divides λ
Proof:
(1) Let h(α) be a cyclotomic prime that divides λ
(2) Using Lemma 2 above, we know that:
(α - 1)(α2 - 1)*...*(αλ-1 - 1) = λ
(3) Since h(α) divides λ, it must divide one of the factors of (αj - 1). [See Definition 4, here]
(4) But then h(α) = α - 1 since (α - 1) is the only prime that divides (αj - 1). [From Lemma 3 above]
QED
Corollary 3.2: (α - 1)λ-1 = λ * unit
Proof:
(1) Using Lemma 2 above,
(α - 1)(α2 - 1)*...*(αλ-1 - 1) = λ
(2) Using Lemma 3 above, we know that each (αj - 1) = (α - 1)*unit.
(3) Since there are λ - 1 factors of the form (αj - 1), this gives us:
λ = (α-1)λ-1*(unit)λ-1
(4) Since a (unit)λ-1 = unit, we have
λ = (α -1)λ-1*unit.
QED
Lemma 4: For each cyclotomic prime h(α) that divides a standard prime p = λ, there exists a set of λ incongruent classes mod h(α)
Proof:
(1) There is only 1 cyclotomic prime that divides λ so h(α) = α - 1. [See Corollary 3.1 above]
(2) So, α ≡ 1 (mod h(α)) [Since h(α) = α - 1]
(3) Let g(α) be a cyclotomic integer.
(4) Then g(α) can be put in the following form (see Lemma 1, here for details):
g(α) = a0 + a1α + ... + aλ-1αλ - 1
(5) This means that g(α) ≡ a0 + a1 + ... + aλ - 1 (mod α - 1)
(6) So, g(α) ≡ an integer (mod h(α)).
(7) It is also clear that if g(α) ≡ x (mod λ) that x is an integer between 0 and λ - 1.
(8) But since h(α) divides λ, it is clear that h(α) must also divide g(α) - x (since λ divides g(α) - x).
QED
In today's blog, I will go into detail into the prime divisor of λ. The important idea here is that λ has only a single prime divisor α - 1 which is also a cyclotomic integer.
In today's blog, I will review some basic properties of α - 1. The content of today's blog is based on Harold M. Edwards' Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.
Lemma 1: if n is an odd prime, then
(x - α)(x - α2)*...*(x - αn-1) = xn-1 + xn-2 + ... + 1
Proof:
(1) From a previous result, we have:
xn - 1 = (x - 1)(x - α)(x - α2)*...*(x - αn-1)
(2) Now xn - 1 divided by x-1 = xn-1 + xn-2 + ... + x + 1 since:
(x-1)(xn-1 + xn-2 + ... + x + 1) =
= xn + xn-1 + xn-2 + .... + x2 + x -xn-1 - xn-2 - .... - x2 - x - 1 =
= xn - 1
(3) Putting #2 and #1 together gives us:
xn-1 + xn-2 + ... + x + 1 = (x - α)(x - α2) * ... * (x - αn-1)
QED
This second lemma uses the result of Lemma 1 to show that the Norm of α - 1 is λ. If you need a review of the norm of cyclotomic integers, see Section 4, here.
Lemma 2: N(α - 1) = λ
Proof:
(1) N(α - 1) = N(1 - α) since:
N(α - 1) = (α - 1)(α2 - 1)*...*(αλ-1 - 1)
N(1 - α) = (-1)λ-1[(α - 1)(α2 - 1)*..*(αλ-1 - 1)
Since λ is odd, λ-1 is even and (-1)λ-1 = 1
(2) N(1 - α) = (1 - α)(1 - α2)*...*(1 - αλ-1) [See here for definition of norm for cyclotomic integers]
(3) From Lemma 1 above:
(x - α)(x - α2)*...*(x - αλ-1) = xλ-1 + xλ-2 + ... + x + 1
(4) Setting x = 1 gives us:
(1 - α)(1 - α2)*...*(1 - αλ-1) = 1λ-1 + 1λ-2 + ... + 1 + 1 = λ
QED
Lemma 3: (αj - 1) = (α - 1)*unit
Proof:
(1) αj - 1= (α - 1)(αj-1 + αj-2 + ... + 1)
(2) Since ab=c → N(a)N(b)=N(c) (See Lemma 6, here), we know that:
N(αj - 1) = N(α-1) * N(αj-1 + αj-2 + ... + 1)
which gives us that:
N(αj-1 + αj-2 + ... + 1) = N(αj - 1)/N(α - 1)
(3) From Lemma 2 above, N(α-1) = λ
(4) We can also conclude from Lemma 2 above that N(αj-1) = λ since (αj-1) is a conjugate of (α - 1).
(5) Therefore, N(αj-1 + αj-2 + ... + 1) = 1 which makes (αj-1 + αj-2 + ... + 1) a unit (see Definition 1, here)
QED
Corollary 3.1: (α -1 ) is the only cyclotomic prime that divides λ
Proof:
(1) Let h(α) be a cyclotomic prime that divides λ
(2) Using Lemma 2 above, we know that:
(α - 1)(α2 - 1)*...*(αλ-1 - 1) = λ
(3) Since h(α) divides λ, it must divide one of the factors of (αj - 1). [See Definition 4, here]
(4) But then h(α) = α - 1 since (α - 1) is the only prime that divides (αj - 1). [From Lemma 3 above]
QED
Corollary 3.2: (α - 1)λ-1 = λ * unit
Proof:
(1) Using Lemma 2 above,
(α - 1)(α2 - 1)*...*(αλ-1 - 1) = λ
(2) Using Lemma 3 above, we know that each (αj - 1) = (α - 1)*unit.
(3) Since there are λ - 1 factors of the form (αj - 1), this gives us:
λ = (α-1)λ-1*(unit)λ-1
(4) Since a (unit)λ-1 = unit, we have
λ = (α -1)λ-1*unit.
QED
Lemma 4: For each cyclotomic prime h(α) that divides a standard prime p = λ, there exists a set of λ incongruent classes mod h(α)
Proof:
(1) There is only 1 cyclotomic prime that divides λ so h(α) = α - 1. [See Corollary 3.1 above]
(2) So, α ≡ 1 (mod h(α)) [Since h(α) = α - 1]
(3) Let g(α) be a cyclotomic integer.
(4) Then g(α) can be put in the following form (see Lemma 1, here for details):
g(α) = a0 + a1α + ... + aλ-1αλ - 1
(5) This means that g(α) ≡ a0 + a1 + ... + aλ - 1 (mod α - 1)
(6) So, g(α) ≡ an integer (mod h(α)).
(7) It is also clear that if g(α) ≡ x (mod λ) that x is an integer between 0 and λ - 1.
(8) But since h(α) divides λ, it is clear that h(α) must also divide g(α) - x (since λ divides g(α) - x).
QED
Tuesday, July 25, 2006
Cyclotomic Integers: Periods mod p
Today's blog continues the details that are used by Ernst Kummer in his theory of ideal numbers. He then uses ideal numbers in his proof for Fermat's Last Theorem for regular primes.
The contents of today's blog are taken from Harold M. Edwards Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.
In previous blogs, I have talked about cyclotomic integers and cyclotomic periods derived from cyclotomic integers. In today's blog, I will focus on a single, very important result. That for any prime p where p ≠ λ, there exists an integer f = exponent mod λ (see definition 2, here) and an integer e = (λ - 1)/f (see definition 3, here).
This means that for any prime p, there exist a set of e cyclotomic periods that each have a length of f elements (see here for review of the basic properties of cyclotomic periods).
Lemma 1: xp - x ≡ (x-1)(x-2)*...*(x-p) ≡ 0 (mod p)
Proof:
(1) Fermat's Little Theorem gives us:
xp-1 ≡ 1 (mod p)
So that:
p divides xp-1 - 1
So that:
x(xp-1 - 1) = xp - x ≡ 0 (mod p)
(2) We also know that:
(x -1)*(x-2)*...(x-p) ≡ 0 (mod p)
(a) There exists a r such that x ≡ r (mod p)
(b) We know that p divides x - r
(c) We also know that r is between 0 and p-1.
(d) if r is 0, then p divides x-p; otherwise, p divides x-r.
(3) Putting (#1) and (#2) together, we have:
xp - x ≡ (x-1)(x-2)*...*(x-p) ≡ 0 (mod p)
QED
Lemma 2: g(α) = g(αp) if and only if g(α) is a cyclotomic integer made up of periods of length f.
Proof:
(1) Let λ be an odd prime.
(2) Let α be a primitive root of unity such that αλ = 1.
(3) Let p be an odd prime distinct from λ
(4) Let τ be mapping such that τα = αp
(5) Let f be the least positive integer for which pf ≡ 1 (mod λ)
(6) We know that f divides λ -1 (see Lemma 1, here)
(7) Let e= (λ-1)/f
(8) Assume that g(α) is made up of periods of length f. [See here for review of cyclotomic periods]
(9) Then, σeg(α) = g(α) [See Lemma 4 here for details.]
(10) Then, there must exist an integer k such that:
τ = σk
Since the primitive root (see here for review if needed) can take all possible values mod λ [By definition σ = a mapping between α and αγ where γ is a primitive root, see here]
(11) Using step #10, we note that:
τf = σkf
Since τf ≡ 1 (mod λ), we know that σkf ≡ 1 (mod λ)
(12) Since the order of λ is λ -1 (see here), we know that kf must be divisible by λ - 1 (see Lemma 2 here) which means it is divisible by ef since ef=λ - 1.
So, ef divides kf means that e must divide k.
(13) So, from step #10 and step #12:
τ is a power of σe
(14) So, there exists k' such that ek' = k.
(15) From #14, we have:
τ = (σ1e)(σ2e)...(σk'e)
and therefore:
τg(α) =(σ1e)(σ2e)...(σk'e)g(α) = g(α)
(16) Assume that τg(α) = g(α)
(17) We know that there exists k such that:
τ = σk [Since σ is a mapping to γ which is a primitive root and the primitive root can take on all values modulo λ]
(18) Since g(α) repeats at τg(α), we know that g(α) consists of e periods of length f. [See Corollary 1.2 here]
(19) By definition, e divides (λ - 1) [See here for definition of periods]
(20) Thus, e is a common divisor of k and λ - 1.
(21) e is the greatest common divisor of k and λ - 1 since:
(a) Let d be an integer that divides both k, λ-1 so that:
k = qd
λ - 1 = df'
(b) Now,
τf' = σkf' = σqdf' = σ(λ - 1)q which is identity[from step #17, #21a, and since σλ-1 is the identity, see here]
(c) So that:
f' ≥ f [Since f is least value where pf ≡ 1 (mod λ)]
d ≤ e [Because d = (λ-1)/f' where f' ≥ f and e=(λ - 1)/f]
(22) Using Bezout's Identity, there exists a,b such that:
e = ak + b(λ - 1)
(23) Further,
σe = σakσb(λ-1) = [from step #22]
= σak = [Since σb(λ-1) is identity]
= τa [Since τ = σk from step #17]
(24) From this, we see that:
σeg(α) = τag(α) = g(α)
QED
Theorem 3: For any cyclotomic integer g(α) made up of periods of length f where f is the exponent mod λ for p, there exists an integer u such that g(α) ≡ u (mod p)
Proof:
(1) From Lemma 1 above, we have:
xp - x ≡ (x-1)(x-2)*...*(x-p) (mod p)
(2) Let x = g(α)
(3) Then:
g(α)p - g(α) ≡ [g(α) - 1][g(α) - 2]*...*[g(α) - p] (mod p)
(4) From a previous result (see Lemma 3 here), where g(α)p ≡ g(αp) (mod p), we have:
g(αp) - g(α) ≡ [g(α) - 1][g(α) - 2]*...*[g(α) - p] (mod p)
(5) Now, since g(α) is made up of periods of length f, we know that g(αp) = g(α) [See Lemma 2 above]
So that:
g(αp) - g(α) = 0 ≡ 0 (mod p)
(9) This gives us:
[g(α) - 1][g(α) - 2][g(α) - 3]*...*[g(α)-p] ≡ 0 (mod p)
(10) So at least one of these values must be divisible by p (otherwise, the product of each g(α) - u could not be 0.)
(11) So there exists an integer u such that p divides g(α) - u
Which means that:
g(α) ≡ u (mod p)
QED
Corollary 3.1: For each of the e cyclotomic periods ηi for a given odd prime p, there exists an integer ui such that ηi ≡ ui (mod p)
Proof:
(1) Each period ηi can be thought of as a cyclotomic integer made up of periods of length f:
g(α) = (0)η0 + ... + (1)ηi + ... + (0)ηe-1 = ηi
(2) From Theorem 3 above, we know that there exists an integer ui such that g(α) ≡ ui (mod p)
(3) So, we see that for each ηi, there exists ui such that:
ηi ≡ ui (mod p)
QED
The contents of today's blog are taken from Harold M. Edwards Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory.
In previous blogs, I have talked about cyclotomic integers and cyclotomic periods derived from cyclotomic integers. In today's blog, I will focus on a single, very important result. That for any prime p where p ≠ λ, there exists an integer f = exponent mod λ (see definition 2, here) and an integer e = (λ - 1)/f (see definition 3, here).
This means that for any prime p, there exist a set of e cyclotomic periods that each have a length of f elements (see here for review of the basic properties of cyclotomic periods).
Lemma 1: xp - x ≡ (x-1)(x-2)*...*(x-p) ≡ 0 (mod p)
Proof:
(1) Fermat's Little Theorem gives us:
xp-1 ≡ 1 (mod p)
So that:
p divides xp-1 - 1
So that:
x(xp-1 - 1) = xp - x ≡ 0 (mod p)
(2) We also know that:
(x -1)*(x-2)*...(x-p) ≡ 0 (mod p)
(a) There exists a r such that x ≡ r (mod p)
(b) We know that p divides x - r
(c) We also know that r is between 0 and p-1.
(d) if r is 0, then p divides x-p; otherwise, p divides x-r.
(3) Putting (#1) and (#2) together, we have:
xp - x ≡ (x-1)(x-2)*...*(x-p) ≡ 0 (mod p)
QED
Lemma 2: g(α) = g(αp) if and only if g(α) is a cyclotomic integer made up of periods of length f.
Proof:
(1) Let λ be an odd prime.
(2) Let α be a primitive root of unity such that αλ = 1.
(3) Let p be an odd prime distinct from λ
(4) Let τ be mapping such that τα = αp
(5) Let f be the least positive integer for which pf ≡ 1 (mod λ)
(6) We know that f divides λ -1 (see Lemma 1, here)
(7) Let e= (λ-1)/f
(8) Assume that g(α) is made up of periods of length f. [See here for review of cyclotomic periods]
(9) Then, σeg(α) = g(α) [See Lemma 4 here for details.]
(10) Then, there must exist an integer k such that:
τ = σk
Since the primitive root (see here for review if needed) can take all possible values mod λ [By definition σ = a mapping between α and αγ where γ is a primitive root, see here]
(11) Using step #10, we note that:
τf = σkf
Since τf ≡ 1 (mod λ), we know that σkf ≡ 1 (mod λ)
(12) Since the order of λ is λ -1 (see here), we know that kf must be divisible by λ - 1 (see Lemma 2 here) which means it is divisible by ef since ef=λ - 1.
So, ef divides kf means that e must divide k.
(13) So, from step #10 and step #12:
τ is a power of σe
(14) So, there exists k' such that ek' = k.
(15) From #14, we have:
τ = (σ1e)(σ2e)...(σk'e)
and therefore:
τg(α) =(σ1e)(σ2e)...(σk'e)g(α) = g(α)
(16) Assume that τg(α) = g(α)
(17) We know that there exists k such that:
τ = σk [Since σ is a mapping to γ which is a primitive root and the primitive root can take on all values modulo λ]
(18) Since g(α) repeats at τg(α), we know that g(α) consists of e periods of length f. [See Corollary 1.2 here]
(19) By definition, e divides (λ - 1) [See here for definition of periods]
(20) Thus, e is a common divisor of k and λ - 1.
(21) e is the greatest common divisor of k and λ - 1 since:
(a) Let d be an integer that divides both k, λ-1 so that:
k = qd
λ - 1 = df'
(b) Now,
τf' = σkf' = σqdf' = σ(λ - 1)q which is identity[from step #17, #21a, and since σλ-1 is the identity, see here]
(c) So that:
f' ≥ f [Since f is least value where pf ≡ 1 (mod λ)]
d ≤ e [Because d = (λ-1)/f' where f' ≥ f and e=(λ - 1)/f]
(22) Using Bezout's Identity, there exists a,b such that:
e = ak + b(λ - 1)
(23) Further,
σe = σakσb(λ-1) = [from step #22]
= σak = [Since σb(λ-1) is identity]
= τa [Since τ = σk from step #17]
(24) From this, we see that:
σeg(α) = τag(α) = g(α)
QED
Theorem 3: For any cyclotomic integer g(α) made up of periods of length f where f is the exponent mod λ for p, there exists an integer u such that g(α) ≡ u (mod p)
Proof:
(1) From Lemma 1 above, we have:
xp - x ≡ (x-1)(x-2)*...*(x-p) (mod p)
(2) Let x = g(α)
(3) Then:
g(α)p - g(α) ≡ [g(α) - 1][g(α) - 2]*...*[g(α) - p] (mod p)
(4) From a previous result (see Lemma 3 here), where g(α)p ≡ g(αp) (mod p), we have:
g(αp) - g(α) ≡ [g(α) - 1][g(α) - 2]*...*[g(α) - p] (mod p)
(5) Now, since g(α) is made up of periods of length f, we know that g(αp) = g(α) [See Lemma 2 above]
So that:
g(αp) - g(α) = 0 ≡ 0 (mod p)
(9) This gives us:
[g(α) - 1][g(α) - 2][g(α) - 3]*...*[g(α)-p] ≡ 0 (mod p)
(10) So at least one of these values must be divisible by p (otherwise, the product of each g(α) - u could not be 0.)
(11) So there exists an integer u such that p divides g(α) - u
Which means that:
g(α) ≡ u (mod p)
QED
Corollary 3.1: For each of the e cyclotomic periods ηi for a given odd prime p, there exists an integer ui such that ηi ≡ ui (mod p)
Proof:
(1) Each period ηi can be thought of as a cyclotomic integer made up of periods of length f:
g(α) = (0)η0 + ... + (1)ηi + ... + (0)ηe-1 = ηi
(2) From Theorem 3 above, we know that there exists an integer ui such that g(α) ≡ ui (mod p)
(3) So, we see that for each ηi, there exists ui such that:
ηi ≡ ui (mod p)
QED
Cyclotomic Integers: Unique Factorization Fails
Unique factorization fails for cyclotomic integers starting with λ = 23 where λ represent the primitive root of unity that a given cyclotomic integer is based on. For details on cyclotomic integers start here. This blog is part of the general proof that shows that Fermat's Last Theorem is true for regular primes.
The content is today's blog is based on Harold M. Edwards' Fermat's Last Theorem: A Genetic Introduction for Algebraic Number Theory. In today's blog, I take one result from Edwards. Edwards goes over a much more complete list of calculations taken from Ernst Kummer's original article.
Theorem 1: Not all cyclotomic integers are characterized by unique factorization
Proof:
(1) The method of this proof is to show that unique factorization fails for the number 47 when λ = 23.
NOTE: We only need to show one case of failure to show that unique factorization fails.
(2) Norm of (1 - α + α21) = 47*139.
NOTE: These calculations are taken directly from Edwards. If you see any mistake, please compare it to Edwards' book for the correction. Edwards takes his calculations from Kummer's original paper.
(a) Nf(α) = f(α)*f(α2)*...*f(αλ-1) [Nf(α) = Norm of f(α) See Definition 2, here]
(b) Let G(α) = f(α)f(α4)f(α-7)f(α-5)f(α3)f(α-11)f(α2)f(α8)f(α9)f(α-10)f(α6)
where α-x = α23-x
(c) Then Nf(α) = G(α)G(α-2)
since G(α-2) = f(α-2)f(α-8)f(α14)f(α10)f(α-6)f(α22)f(α-4)f(α-16)f(α-18)f(α20)f(α-12)
To be clear:
G(α) = f(α)f(α4)f(α16)f(α18)f(α3)f(α12)f(α2)f(α8)f(α9)f(α13)f(α6)
G(α-2) = f(α21)f(α15)f(α14)f(α10)f(α17)f(α22)f(α19)f(α7)f(α5)f(α20)f(α11)
(d) Let:
g(α) = f(α)f(α4)
h(α) = g(α)f(α-7)
(e) Then:
G(α) = h(α)h(α-5)h(α2)g(α-10)
since this equals:
[f(α)f(α4)f(α16)][f(α18)f(α3)f(α12)][f(α2)f(α8)f(α9)][f(α13)f(α6)]
(f) Now, we can do the following computations:
g(α) = f(α)f(α4) = (1 - α + α21)(1 - α4 + α15) =
= α21 - α16 + α15 + α13 + α5 - α4 - α2 - α + 1.
h(α) = g(α)f(α-7) =
= (α21 - α16 + α15 + α13 + α5 - α4 - α2 - α + 1)(1 - α16 + α10) =
= α20 + α19 + α17 -3α16 + α13 + α12 + α9 - α8 - α7 + α5 - α2 - α + 1.
h(α-5) = α15 + α20 + α7 - 3α12 + α4 + α9 + α - α6 - α11 + α21 - α13 - α18 + 1.
h(α2) = α17 + α15 + α11 - 3α9 + α3 + α + α18 - α16 - α14 + α10 - α4 - α2 + 1
g(α-10) = α20 - α + α11 + α8 + α19 - α6 - α3 - α13 + 1
(g) So, G(α) = -44 + 15θ0 - 13θ1
where θ0 = α + α4 + α-7 + ... + α6 and θ1 = -1 - θ0.
(h) Now, we can check it to find:
θ0θ1 = 11 + 5θ0 + 5θ1 = 6.
(i) Now, we are ready to put the calculation all together so that:
N(1 - α + α21) = G(α)G(α-2) =
= (-31 + 28θ0)(-31 + 28θ1) = 312 - 31*28(θ0 + θ1) + 6*282 = 961 + 868 + 4704 = 6533 = 47*139.
(3) Norm(47) = 47*47*....*47 = 4722.
(4) Norm(139) = 139*139*...*139 = 13922
(5) But, then (1 - α + α21) doesn't divide 47 and (1 - α + α21) doesn't divide 139 since (from Lemma 6, here), a cyclotomic only divides another cyclotomic integer if the norm of the first cyclotomic integer divides the norm of the second cyclotomic integer.
NOTE: In other words, 47*139 does not divide 13922 and likewise, 47*139 does not divide 4722.
(6) And this violates Euclid's Lemma since (1 - α + α21) does divide 47*139 by the equation in step #2 but it doesn't divide 47 and it doesn't divide 139.
NOTE: The equation proved in step #2 is:
N(1 - α + α21) = (1 - α + α21)*(1 - α2 + α21)*...*(1 - α21 + α21) = 47*139.
(7) And this means that unique factorization does not exist in this situation. [See here for details on the Fundamental Theorem of Arithmetic and its dependence on Euclid's Lemma]
QED
Kummer then developed his theory of ideal numbers in order to save unique factorization for cyclotomic integers.
The content is today's blog is based on Harold M. Edwards' Fermat's Last Theorem: A Genetic Introduction for Algebraic Number Theory. In today's blog, I take one result from Edwards. Edwards goes over a much more complete list of calculations taken from Ernst Kummer's original article.
Theorem 1: Not all cyclotomic integers are characterized by unique factorization
Proof:
(1) The method of this proof is to show that unique factorization fails for the number 47 when λ = 23.
NOTE: We only need to show one case of failure to show that unique factorization fails.
(2) Norm of (1 - α + α21) = 47*139.
NOTE: These calculations are taken directly from Edwards. If you see any mistake, please compare it to Edwards' book for the correction. Edwards takes his calculations from Kummer's original paper.
(a) Nf(α) = f(α)*f(α2)*...*f(αλ-1) [Nf(α) = Norm of f(α) See Definition 2, here]
(b) Let G(α) = f(α)f(α4)f(α-7)f(α-5)f(α3)f(α-11)f(α2)f(α8)f(α9)f(α-10)f(α6)
where α-x = α23-x
(c) Then Nf(α) = G(α)G(α-2)
since G(α-2) = f(α-2)f(α-8)f(α14)f(α10)f(α-6)f(α22)f(α-4)f(α-16)f(α-18)f(α20)f(α-12)
To be clear:
G(α) = f(α)f(α4)f(α16)f(α18)f(α3)f(α12)f(α2)f(α8)f(α9)f(α13)f(α6)
G(α-2) = f(α21)f(α15)f(α14)f(α10)f(α17)f(α22)f(α19)f(α7)f(α5)f(α20)f(α11)
(d) Let:
g(α) = f(α)f(α4)
h(α) = g(α)f(α-7)
(e) Then:
G(α) = h(α)h(α-5)h(α2)g(α-10)
since this equals:
[f(α)f(α4)f(α16)][f(α18)f(α3)f(α12)][f(α2)f(α8)f(α9)][f(α13)f(α6)]
(f) Now, we can do the following computations:
g(α) = f(α)f(α4) = (1 - α + α21)(1 - α4 + α15) =
= α21 - α16 + α15 + α13 + α5 - α4 - α2 - α + 1.
h(α) = g(α)f(α-7) =
= (α21 - α16 + α15 + α13 + α5 - α4 - α2 - α + 1)(1 - α16 + α10) =
= α20 + α19 + α17 -3α16 + α13 + α12 + α9 - α8 - α7 + α5 - α2 - α + 1.
h(α-5) = α15 + α20 + α7 - 3α12 + α4 + α9 + α - α6 - α11 + α21 - α13 - α18 + 1.
h(α2) = α17 + α15 + α11 - 3α9 + α3 + α + α18 - α16 - α14 + α10 - α4 - α2 + 1
g(α-10) = α20 - α + α11 + α8 + α19 - α6 - α3 - α13 + 1
(g) So, G(α) = -44 + 15θ0 - 13θ1
where θ0 = α + α4 + α-7 + ... + α6 and θ1 = -1 - θ0.
(h) Now, we can check it to find:
θ0θ1 = 11 + 5θ0 + 5θ1 = 6.
(i) Now, we are ready to put the calculation all together so that:
N(1 - α + α21) = G(α)G(α-2) =
= (-31 + 28θ0)(-31 + 28θ1) = 312 - 31*28(θ0 + θ1) + 6*282 = 961 + 868 + 4704 = 6533 = 47*139.
(3) Norm(47) = 47*47*....*47 = 4722.
(4) Norm(139) = 139*139*...*139 = 13922
(5) But, then (1 - α + α21) doesn't divide 47 and (1 - α + α21) doesn't divide 139 since (from Lemma 6, here), a cyclotomic only divides another cyclotomic integer if the norm of the first cyclotomic integer divides the norm of the second cyclotomic integer.
NOTE: In other words, 47*139 does not divide 13922 and likewise, 47*139 does not divide 4722.
(6) And this violates Euclid's Lemma since (1 - α + α21) does divide 47*139 by the equation in step #2 but it doesn't divide 47 and it doesn't divide 139.
NOTE: The equation proved in step #2 is:
N(1 - α + α21) = (1 - α + α21)*(1 - α2 + α21)*...*(1 - α21 + α21) = 47*139.
(7) And this means that unique factorization does not exist in this situation. [See here for details on the Fundamental Theorem of Arithmetic and its dependence on Euclid's Lemma]
QED
Kummer then developed his theory of ideal numbers in order to save unique factorization for cyclotomic integers.
Subscribe to:
Posts (Atom)
