Cyclotomic Integers: Prime Divisors
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: 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
Proposition 2: Given λ, p, f, e, there exist integers u1, u2, ..., ue with the property that equation satisfied by the periods η of length f is satisfied as a congruence modulo p by the integers ui.
Proof:
(1) Let us start with cyclotomic integers of the form j - ηi where j = 1, 2, ..., p and i = 1, 2, ..., e.
(2) We can see that there are e*p elements of the form in step #1.
(3) First, we choose one of these integers that is not divisible by p. For example, we can choose p - ηi where i is any value 1, 2, .., e.
(4) We repeat this step until we have selected all the cyclotomic integers that are not divisible by p. Let us assume that there are n of them that have been selected.
(5) Let ψ(η) be defined as the product of all these n selected cyclotomic integers.
NOTE: I use this notation straight from Edwards. The meaning is just a cyclotomic integer that is composed of the product described.
(6) By Lemma 1 above, we know that:
(ηi - 1)(ηi - 2)*...*(ηi - p) ≡ ηip - ηi ≡ 0 (mod p)
(7) We know for each i, there is at least one factor j - ηi that is not in ψ(η) otherwise we are in a situation like step #6 and ψ(η) would be divisible by p which it is not.
(8) Let ui - ηi, for i = 1, 2, ..., e denote a factor of the form j - ηi that is not in ψ(η)
NOTE: In other words, for each factor i in step #7, ui = j such that j - ηi is divisible by p.
(9) Then (j - ηi)ψ(η) ≡ 0 ≡ (ui - ηi)ψ(η) (mod p.)
(10) Since ui = j, we also have:
(j - ui)ψ(η) ≡ 0 (mod p)
(11) Further, there is only 1 integer between 1 and p for ui - ηi is not in ψ(η) since:
(a) Assume j ≠ u but (j-u) ≡ 0 (mod p)
(b) Since j,u lie in the range 1 ≤ j,u ≤ p, j - u then since the integers modulo p are a group on multiplication (see Theorem, here), there must exist an integer b such that b is the inverse of (j-u)
So that:
b(j-u) ≡ 1 (mod p)
(d) From which ψ(η) ≡ b(j-u)ψ(η) ≡ 0 (mod p) which is a contradiction.
(e) So we reject (a).
(12) From step #11, we can see that there are exactly ep-e factors that make up ψ(η), namely, all the j - ηi except for the factors ui - ηi
QED
Corollary 2.1:
In Proposition 2 above, ui are such that if F(η1, η2, ... , ηe) is any polynomial expression in the η's with integer coefficients and if the cyclotomic integer F(η1, η2, ..., ηe) is 0, then the integer F(u1, u2, ..., ue) obtained by substituting ui in place of ηi (i = 1, 2, 3, ..., e) satisfies F(u1, u2, ..., ue) ≡ 0 (mod p).
Proof:
(1) From, the Proposition:
ηiψ(η) ≡ uiψ(η) (mod p) for i = 1,2, ..., e. [Since, ui - ηi ≡ 0 (mod p) → ψ(η)[ui - ηi] ≡ uiψ(η) - ηiψ(η) ≡ 0 (mod p)]
(2) Therefore F(η1, η2, ..., ηe)ψ(η) ≡ F(u1, u2, ..., ue)ψ(η) mod p for any polynomial F(η1, η2, ..., ηe) in periods since the congruence mod p is consistent with addition and multiplication (see here for details)
(3) If F(η1, η2, ..., ηe) = 0, then F(u1, u2, ..., ue)ψ(η) ≡ 0 (mod p) from step #2.
(4) We know that ψ(η) is not congruent to 0 (mod p)
(5) So, from step #3 and step #4, we see that F(u1, u2, ..., ue) ≡ 0 (mod p)
QED
Definition 1: A prime congruence relation
A congruence relation is said to be prime if a product is congruent to 0 only if one of its factors is congruent to 0.
NOTE: One of the ideas that I talk about here is the set of incongruent cyclotomic integers in relation to this congruence relation. By this, I mean, the set of all distinct cyclotomic integers such that if ~ is the prime congruence relation, a~b, then there exists an element c in the set of incongruent cyclotomic integers in relation to this congruence relation such that a~c and b~c.
Theorem 3:
Based on Proposition 2 above, 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. Finally, the number of incongruent elements is exactly pf
NOTE: Moreover, this congruence relation is prime in the sense that the product can be congruent to 0 only if one of the factors is (See definition 1 above)
Proof:
(1) From Proposition 2 above, we can assume that the following exist:
ψ(η): 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.
(2) We can define a congruence relation ≡ in the following way:
Let g(α) ≡ φ(α) mean g(α)ψ(η) ≡ φ(α)ψ(η) mod p.
(3) The relation ≡ (defined in step #3) is clearly reflexive, symmetric, transitive, and consistent with addition and multiplication. (See here to review modular arithmetic if needed)
(4) We also see that p ≡ 0 and from the proposition 2 above, ηi ≡ ui.
(5) Since ψ(η) is not congruent to 0 mod p, 1 is not ≡ to 0.
(6) 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.
(7) 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.
(8) Therefore, there are at most pf incongruent cyclotomic integers modulo the congruence relation ~. [From step #7, see Corollary 2.1, here]
(9) Assume that ~ is not prime.
(10) This means that there exists ψ1(α), ψ2(α) such that ψ1(α)ψ2(α) ~ 0 but ψ1(α) not ~ 0 and ψ2(α) not ~ 0.
(11) We can define another congruence relation ~2 such that:
g(α) ~2 φ(α) if and only if g(α)ψ1(α) ~ φ(α)ψ1(α)
(12) 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.
(13) We can also see that this relation has fewer incongruent integers from ~ since:
ψ2(α) ~2 0 but ψ2(α) not ~ 0 (by step #10 above)
(14) So ~2, we see has pf-1 incongruent cyclotomic integers; that is, it has at least 1 less than ~.
(15) Now, if ~2 is not prime, then we repeat the steps #10 thru #14, 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.
(16) So, we can assume that there exists a congruent relation ~n with all the properties of ~ which is prime.
(17) Now, we can also see that set of cyclotomic integers that make up the congruence relation ~n is a subgroup to the additive group of cyclotomic integers mod p since:
NOTE: This only works because ~ is prime. If ~ were not prime, then we cannot meaningfully talk about the set of cyclotomic integers that make up the congruence relation being a subgroup of cyclotomic integers mod p.
For example, if ab~0 but a not ~0 and b not~0, then we have a situation a,b are not divisible by p but ab is which is impossible since p is a prime.
(a) Let g(α) be a cyclotomic integer.
(b) Then, there exists r(α) such that g(α) ~n 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.
(18) 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.
(19) the number of incongruent cyclotomic integers is greater than 1 (because 1 not ~ 0 so there is at least two)
(20) 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.
(21) 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]
(22) 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]
(23) 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.
(24) Since ≡ has all the properties assumed for ~ it follows that ≡ coincides with ~.
QED
Definition 2: Congruence modulo the prime divisor of p corresponding to u1, u2, ..., ue.
This is the congruence relation specified in Theorem 2 above. If g(α) is congruent to 0 modulo this relation then g(α) will be said to be divisible by the prime divisor of p corresponding to u1, u2, ..., ue
Theorem 4:
For a given λ, p, f, e, let u1, u2, ..., ue and u1, u2, ..., ue be any two sets of integers with the property specified in the proposition above. Then there is one and only one integer k, 0 ≤ k ≤ e-1 such that congruence modulo the prime divisor of p corresponding to u1, u2, ..., ue coincides with congruence modulo the prime divisor of p corresponding to u1+k, u2+k, ..., uk where, as usual, uj = uj+e by definition. Thus there are precisely e distinct congruence relations of the type described in Theorem 2 above. Divisibility by p is equivalent to divisibility by all e of these prime divisors of p; that is, a cyclotomic integer g(α) is divisible by p in the ordinary sense if and only if it is divisible by all e prime divisors of p in the sense just defined.
Proof:
(1) Let u1, u2, ..., ue be a set of integers yielded by the construction in the proof of the proposition 2 above.
(2) Let u1, u2, ..., ue be any set of integers satisfying the conditions of proposition 2 above.
(3) For a given λ and a given factor of λ-1, we have a set of e periods (see here for review) which we can label:
η1, η2, ..., ηe
where each period consists of the following:
(a) η1 = α + σeα + σ2eα + ... + σλ-1-eα
(b) ηi+1 = σηi
(4) Let us consider now the product of η1 with an arbitrary period ηi:
η1ηi = c0 + c1η1 + c2η2 + ... + ceηe
where ci are all rational integers since this is really counting the number of times each period results from the combinition.
(5) From a previous result (see Lemma 3, here), we know that periods consist of f elements where f = (λ-1)/e.
(6) We can then take the equation in step #4 and count the number of products that result since:
(a) Each ηi consists of f components (step #5)
(b) So the number of components for η1ηi is:
(f)(f) = f2 = c0(1) + c1(f) + ... + ce(f)
NOTE: We can do this since ci is just the number of times a given term occurs and since the product of periods is itself a sum of periods (see Corollary 4.1, here).
(7) Now, c0 ≠ 0 only if at least one term αμ of ηi is the inverse of the term α-μ in η1. [Otherwise, all products correspond to some αl where l ≠ 0.]
(8) But when this is the case ηi contains the inverse σνeαμ of every term σνeα-μ in η1 [Since each period corresponds to a set of elements which stay the same after each σe. See Lemma 2, here for more information on σe]
(9) Therefore c0 = f for this one value of i (as mentioned in step #8) and c0=0 for all other values of i. [It equals f, since there are f elements that get added together as part of step #7] So that:
For one value of i, then c0 = f giving us:
c1 + c2 + ... + ce = f[c1 + c2 + ... + ce]/f = (f2 - f)/f = f-1.
For all others c0 = 0 giving us:
c1 + c2 + ... + ce = f[c1 + c2 + ... + ce]/f = f2/f = f.
NOTE: Where this occurs depends on the size of f. If f is even, i=0, if f is odd, then i =(1/2)e.
(10) Using σ notation (see here), we can generalize our result in step #4:
η1ηi + η2ηi+1 + ... + ηeηi-1 = η1ηi + σ(η1ηi) + ... + σe-1(η1ηi)
(11) Using the result in step #10 and combining it with the result in step #6 gives us:
η1ηi + σ(η1ηi) + ... + σe-1(η1ηi) =
= ec0 + c1(η1 + η2 + ... + ηe) + ... + ce(ηe + η1 + ... + ηe-1) =
= ec0 + (c1 + c2 + ... + ce)(ηe + η1 + ... + ηe-1)
(12) Remembering that = α + α2 + ... + αλ-1 gives us ( Lemma 2, here):
η1 + η2 + ... + ηe = -1.
(13) Applying the result in step #12 to step #11 gives us:
= ec0 - (c1 + c2 + ... + ce)
(14) So that applying step # 9 gives us:
either:
0 - f = -f [in all but one case for i]
or
ef - (f-1) = λ - 1 -f + 1 = λ - f [in one case for i]
(15) This gives us:
f + η1ηf + η2ηj+1 + ... + ηeηj-1 = λ (in one case) or 0 (in all other cases).
(16) Now, using the fact that ηi ≡ ui (mod p) gives us:
f + u1ui + u2ui+1 + ... + ueui-1 not ≡ 0 (mod p) in 1 case and ≡ 0 (mod p) in all other cases.
(17) If there were a k such that ui ≡ ui+k (mod p) for all i then:
f + u1ui + u2ui+1 + ... + ueui-1 ≡ f + u1ui+k + u2ui+k+1 + ... + ueui+k-1 (mod p)
(18) But, if we choose i = the 1 case where the equation in step #16 not ≡ 0, we have a problem since this means i+k must ≡ 0 unless k ≡ 0 (mod e) since ui+e = ue since periods are unchanged by σe.
(19) This proves that the e cyclic permutations of the u's are all distinct. That is, if ui ≡ ui+k (mod p) then k ≡ 0 (mod e).
(20) Next, consider M = ψ(η) + σψ(η) + ... + σe-1ψ(η) where σ is the conjugation α → αγ which carries ηi to ηi+1. and ψ(η) is the product set defined in the proposition.
(21) Since σM = M, it is clear that M is an ordinary integer.
NOTE: One might also wonder about the possibility where M = d + cα + cα2 + ... + cαλ-1. Since α + α2 + ... + αλ-1= -1, this really gives us d - c which is still an ordinary integer.
(22) Now,
Mψ(η) = ψ(η)ψ(η) + [ σψ(η)] * ψ(η) + ... + [ σe-1ψ(η)]*ψ(η) ≡
≡ ψ(u)ψ(η) + [σψ(u)]ψ(η) + ... + [σe-1ψ(u)]*ψ(η) mod p.
where σkψ(u) denotes the integer obtained by applying σk to ψ(η) and setting η1 = u1, η2 = u2, ..., ηe = ue in the result.
(23) In short, σkψ(u) = ∏(j - ui+k) where i = 1, 2, ..., e and j ranges over all integers from 1 to p except ui.
NOTE: This is clear based on the definition of ψ(u) = ∏(j - ui)
(24) By what was just shown, σkψ(u) contains a factor of 0 (namely a factor ui+k -ui+k) unless k=0, in which case σkψ(u) = ψ(u).
NOTE: The reason for this is when the value ψ(η) was constructed, we skipped the value ηi and in doing this, we also skipped ui With σk, we are now creating a situation where each ui is shifted to ui+k so in this context, ui-k which we didn't skip before now becomes ui-k+k = ui.
(25) Therefore Mψ(η) ≡ ψ(u)ψ(η) not ≡ 0 (mod p) because ψ(u) not ≡ 0 (mod p).
NOTE: ψ(u) is a product of ep-e integers, none of them divisible by p. So in the definition of Mψ(η) all σkψ(u) = 0 so Mψ(η) not ≡ 0 (mod p) because ψ(u)ψ(η) not ≡ 0 (mod p).
(26) Further, M not ≡ 0 (mod p) since only ψ(η) not ≡ 0 (mod p).
(27) If u1, u2, ..., uesatisfy the condition of the proposition, then M ≡ ψ(u) + σ ψ(u) + ... + σe-1ψ(u) mod p since they follow the same relations as ui.
(28) Since M not ≡ 0 (mod p), this implies σkψ(u) not ≡ 0 (mod p) for at least one k.
(29) That is, ∏(j - ui+k) not ≡ 0 (mod p) for at least one k, where i = 1, 2, ..., e and j assumes all values 1, 2, ..., p except ui.
NOTE: If this mapping did not occur then M ≡ 0 (mod p) which is contradicts our assumption that ui has satisfies all the equations of ui.
(30) This implies that ui ≡ ui+k (mod p) and the u's are a cyclic permutation of the u's as was to be shown.
(35) Finally, it remains to show that to say g(α) ≡ 0 (mod p) if and only if g(α) is divisible by all e of the prime divisors that have now been defined.
So, we need to show:
(a) Division by p implies division by all e of the prime divisors.
(b) Division by all e of the prime divisions implies division by p.
(36) Since p is divisible by all e of them, divisions by p implies division by all e of the prime divisors since congruence modulo a prime divisor is consistent with multiplication.
NOTE: See details on proposition 2 above if more information is needed.
(37) Conversely, it was shown in the proof of Theorem 3 above that divisibility of g(α) by the prime divisor of p corresponding to u1, u2, ..., ue is equivalent to g(α)ψ(η) ≡ 0 (mod p) where ψ(η) is the product of ep-e factors j - ηi in which j ≠ ui.
(38) Divisibility of g(α) by the prime divisor of p corresponding to uk+1, uk+2, ... , uk is equivalent to g(α)σ-kψ(η) ≡ 0 mod p because:
σ-kψ(η) = σ-k[ (i=1,e)∏ (j=1,p)∏ (j - ηi)/[(i=1,e)∏ (ui - ηi)]] =
= (i=1,e)∏ (j=1,p)∏ (j - ηi-k)/(i=1,e)∏(ui - ηi-k) =
= (i=1,e)∏ (j=1,p)∏ (j - ηi)/(i=1,e)∏(ui+k - ηi)
(39) That is, σ-kψ(η) is the ψ(η) that results from replacing u1, u2, ..., ue with u1+k, u2+k, ..., uk.
(40) Therefore, if g(α) is divisible by all e prime divisors of p, then g(α)σ-kψ(η) ≡ 0 (mod p) for all k = 0, 1, ..., e-1.
(41) The sum of these congruences gives g(α)*M ≡ 0 (mod p) which, because M ≠ 0 mod p implies g(α) ≡ 0 (mod p) as was to be shown.
QED
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
Proposition 2: Given λ, p, f, e, there exist integers u1, u2, ..., ue with the property that equation satisfied by the periods η of length f is satisfied as a congruence modulo p by the integers ui.
Proof:
(1) Let us start with cyclotomic integers of the form j - ηi where j = 1, 2, ..., p and i = 1, 2, ..., e.
(2) We can see that there are e*p elements of the form in step #1.
(3) First, we choose one of these integers that is not divisible by p. For example, we can choose p - ηi where i is any value 1, 2, .., e.
(4) We repeat this step until we have selected all the cyclotomic integers that are not divisible by p. Let us assume that there are n of them that have been selected.
(5) Let ψ(η) be defined as the product of all these n selected cyclotomic integers.
NOTE: I use this notation straight from Edwards. The meaning is just a cyclotomic integer that is composed of the product described.
(6) By Lemma 1 above, we know that:
(ηi - 1)(ηi - 2)*...*(ηi - p) ≡ ηip - ηi ≡ 0 (mod p)
(7) We know for each i, there is at least one factor j - ηi that is not in ψ(η) otherwise we are in a situation like step #6 and ψ(η) would be divisible by p which it is not.
(8) Let ui - ηi, for i = 1, 2, ..., e denote a factor of the form j - ηi that is not in ψ(η)
NOTE: In other words, for each factor i in step #7, ui = j such that j - ηi is divisible by p.
(9) Then (j - ηi)ψ(η) ≡ 0 ≡ (ui - ηi)ψ(η) (mod p.)
(10) Since ui = j, we also have:
(j - ui)ψ(η) ≡ 0 (mod p)
(11) Further, there is only 1 integer between 1 and p for ui - ηi is not in ψ(η) since:
(a) Assume j ≠ u but (j-u) ≡ 0 (mod p)
(b) Since j,u lie in the range 1 ≤ j,u ≤ p, j - u then since the integers modulo p are a group on multiplication (see Theorem, here), there must exist an integer b such that b is the inverse of (j-u)
So that:
b(j-u) ≡ 1 (mod p)
(d) From which ψ(η) ≡ b(j-u)ψ(η) ≡ 0 (mod p) which is a contradiction.
(e) So we reject (a).
(12) From step #11, we can see that there are exactly ep-e factors that make up ψ(η), namely, all the j - ηi except for the factors ui - ηi
QED
Corollary 2.1:
In Proposition 2 above, ui are such that if F(η1, η2, ... , ηe) is any polynomial expression in the η's with integer coefficients and if the cyclotomic integer F(η1, η2, ..., ηe) is 0, then the integer F(u1, u2, ..., ue) obtained by substituting ui in place of ηi (i = 1, 2, 3, ..., e) satisfies F(u1, u2, ..., ue) ≡ 0 (mod p).
Proof:
(1) From, the Proposition:
ηiψ(η) ≡ uiψ(η) (mod p) for i = 1,2, ..., e. [Since, ui - ηi ≡ 0 (mod p) → ψ(η)[ui - ηi] ≡ uiψ(η) - ηiψ(η) ≡ 0 (mod p)]
(2) Therefore F(η1, η2, ..., ηe)ψ(η) ≡ F(u1, u2, ..., ue)ψ(η) mod p for any polynomial F(η1, η2, ..., ηe) in periods since the congruence mod p is consistent with addition and multiplication (see here for details)
(3) If F(η1, η2, ..., ηe) = 0, then F(u1, u2, ..., ue)ψ(η) ≡ 0 (mod p) from step #2.
(4) We know that ψ(η) is not congruent to 0 (mod p)
(5) So, from step #3 and step #4, we see that F(u1, u2, ..., ue) ≡ 0 (mod p)
QED
Definition 1: A prime congruence relation
A congruence relation is said to be prime if a product is congruent to 0 only if one of its factors is congruent to 0.
NOTE: One of the ideas that I talk about here is the set of incongruent cyclotomic integers in relation to this congruence relation. By this, I mean, the set of all distinct cyclotomic integers such that if ~ is the prime congruence relation, a~b, then there exists an element c in the set of incongruent cyclotomic integers in relation to this congruence relation such that a~c and b~c.
Theorem 3:
Based on Proposition 2 above, 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. Finally, the number of incongruent elements is exactly pf
NOTE: Moreover, this congruence relation is prime in the sense that the product can be congruent to 0 only if one of the factors is (See definition 1 above)
Proof:
(1) From Proposition 2 above, we can assume that the following exist:
ψ(η): 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.
(2) We can define a congruence relation ≡ in the following way:
Let g(α) ≡ φ(α) mean g(α)ψ(η) ≡ φ(α)ψ(η) mod p.
(3) The relation ≡ (defined in step #3) is clearly reflexive, symmetric, transitive, and consistent with addition and multiplication. (See here to review modular arithmetic if needed)
(4) We also see that p ≡ 0 and from the proposition 2 above, ηi ≡ ui.
(5) Since ψ(η) is not congruent to 0 mod p, 1 is not ≡ to 0.
(6) 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.
(7) 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.
(8) Therefore, there are at most pf incongruent cyclotomic integers modulo the congruence relation ~. [From step #7, see Corollary 2.1, here]
(9) Assume that ~ is not prime.
(10) This means that there exists ψ1(α), ψ2(α) such that ψ1(α)ψ2(α) ~ 0 but ψ1(α) not ~ 0 and ψ2(α) not ~ 0.
(11) We can define another congruence relation ~2 such that:
g(α) ~2 φ(α) if and only if g(α)ψ1(α) ~ φ(α)ψ1(α)
(12) 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.
(13) We can also see that this relation has fewer incongruent integers from ~ since:
ψ2(α) ~2 0 but ψ2(α) not ~ 0 (by step #10 above)
(14) So ~2, we see has pf-1 incongruent cyclotomic integers; that is, it has at least 1 less than ~.
(15) Now, if ~2 is not prime, then we repeat the steps #10 thru #14, 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.
(16) So, we can assume that there exists a congruent relation ~n with all the properties of ~ which is prime.
(17) Now, we can also see that set of cyclotomic integers that make up the congruence relation ~n is a subgroup to the additive group of cyclotomic integers mod p since:
NOTE: This only works because ~ is prime. If ~ were not prime, then we cannot meaningfully talk about the set of cyclotomic integers that make up the congruence relation being a subgroup of cyclotomic integers mod p.
For example, if ab~0 but a not ~0 and b not~0, then we have a situation a,b are not divisible by p but ab is which is impossible since p is a prime.
(a) Let g(α) be a cyclotomic integer.
(b) Then, there exists r(α) such that g(α) ~n 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.
(18) 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.
(19) the number of incongruent cyclotomic integers is greater than 1 (because 1 not ~ 0 so there is at least two)
(20) 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.
(21) 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]
(22) 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]
(23) 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.
(24) Since ≡ has all the properties assumed for ~ it follows that ≡ coincides with ~.
QED
Definition 2: Congruence modulo the prime divisor of p corresponding to u1, u2, ..., ue.
This is the congruence relation specified in Theorem 2 above. If g(α) is congruent to 0 modulo this relation then g(α) will be said to be divisible by the prime divisor of p corresponding to u1, u2, ..., ue
Theorem 4:
For a given λ, p, f, e, let u1, u2, ..., ue and u1, u2, ..., ue be any two sets of integers with the property specified in the proposition above. Then there is one and only one integer k, 0 ≤ k ≤ e-1 such that congruence modulo the prime divisor of p corresponding to u1, u2, ..., ue coincides with congruence modulo the prime divisor of p corresponding to u1+k, u2+k, ..., uk where, as usual, uj = uj+e by definition. Thus there are precisely e distinct congruence relations of the type described in Theorem 2 above. Divisibility by p is equivalent to divisibility by all e of these prime divisors of p; that is, a cyclotomic integer g(α) is divisible by p in the ordinary sense if and only if it is divisible by all e prime divisors of p in the sense just defined.
Proof:
(1) Let u1, u2, ..., ue be a set of integers yielded by the construction in the proof of the proposition 2 above.
(2) Let u1, u2, ..., ue be any set of integers satisfying the conditions of proposition 2 above.
(3) For a given λ and a given factor of λ-1, we have a set of e periods (see here for review) which we can label:
η1, η2, ..., ηe
where each period consists of the following:
(a) η1 = α + σeα + σ2eα + ... + σλ-1-eα
(b) ηi+1 = σηi
(4) Let us consider now the product of η1 with an arbitrary period ηi:
η1ηi = c0 + c1η1 + c2η2 + ... + ceηe
where ci are all rational integers since this is really counting the number of times each period results from the combinition.
(5) From a previous result (see Lemma 3, here), we know that periods consist of f elements where f = (λ-1)/e.
(6) We can then take the equation in step #4 and count the number of products that result since:
(a) Each ηi consists of f components (step #5)
(b) So the number of components for η1ηi is:
(f)(f) = f2 = c0(1) + c1(f) + ... + ce(f)
NOTE: We can do this since ci is just the number of times a given term occurs and since the product of periods is itself a sum of periods (see Corollary 4.1, here).
(7) Now, c0 ≠ 0 only if at least one term αμ of ηi is the inverse of the term α-μ in η1. [Otherwise, all products correspond to some αl where l ≠ 0.]
(8) But when this is the case ηi contains the inverse σνeαμ of every term σνeα-μ in η1 [Since each period corresponds to a set of elements which stay the same after each σe. See Lemma 2, here for more information on σe]
(9) Therefore c0 = f for this one value of i (as mentioned in step #8) and c0=0 for all other values of i. [It equals f, since there are f elements that get added together as part of step #7] So that:
For one value of i, then c0 = f giving us:
c1 + c2 + ... + ce = f[c1 + c2 + ... + ce]/f = (f2 - f)/f = f-1.
For all others c0 = 0 giving us:
c1 + c2 + ... + ce = f[c1 + c2 + ... + ce]/f = f2/f = f.
NOTE: Where this occurs depends on the size of f. If f is even, i=0, if f is odd, then i =(1/2)e.
(10) Using σ notation (see here), we can generalize our result in step #4:
η1ηi + η2ηi+1 + ... + ηeηi-1 = η
(11) Using the result in step #10 and combining it with the result in step #6 gives us:
= ec0 + c1(η1 + η2 + ... + ηe) + ... + ce(ηe + η1 + ... + ηe-1) =
= ec0 + (c1 + c2 + ... + ce)(ηe + η1 + ... + ηe-1
(12) Remembering that
(13) Applying the result in step #12 to step #11 gives us:
(14) So that applying step # 9 gives us:
either:
0 - f = -f [in all but one case for i]
or
ef - (f-1) = λ - 1 -f + 1 = λ - f [in one case for i]
f + η1ηf + η2ηj+1 + ... + ηeηj-1 = λ (in one case) or 0 (in all other cases).
(16) Now, using the fact that ηi ≡ ui (mod p) gives us:
f + u1ui + u2ui+1 + ... + ueui-1 not ≡ 0 (mod p) in 1 case and ≡ 0 (mod p) in all other cases.
(17) If there were a k such that ui ≡ ui+k (mod p) for all i then:
f + u1ui + u2ui+1 + ... + ueui-1 ≡ f + u1ui+k + u2ui+k+1 + ... + ueui+k-1 (mod p)
(18) But, if we choose i = the 1 case where the equation in step #16 not ≡ 0, we have a problem since this means i+k
(19) This proves that the e cyclic permutations of the u's are all distinct. That is, if ui ≡ ui+k (mod p) then k ≡ 0 (mod e).
(21) Since σM = M, it is clear that M is an ordinary integer.
NOTE: One might also wonder about the possibility where M = d + cα + cα2 + ... + cαλ-1. Since α + α2 + ... + αλ-1= -1, this really gives us d - c which is still an ordinary integer.
(22) Now,
Mψ(η) = ψ(η)ψ(η) + [ σψ(η)] * ψ(η) + ... + [ σe-1ψ(η)]*ψ(η) ≡
≡ ψ(u)ψ(η) + [σψ(u)]ψ(η) + ... + [σe-1ψ(u)]*ψ(η) mod p.
where σkψ(u) denotes the integer obtained by applying σk to ψ(η) and setting η1 = u1, η2 = u2, ..., ηe = ue in the result.
(23) In short, σkψ(u) = ∏(j - ui+k) where i = 1, 2, ..., e and j ranges over all integers from 1 to p except ui.
NOTE: This is clear based on the definition of ψ(u) =
(24) By what was just shown, σkψ(u) contains a factor of 0 (namely a factor ui+k -ui+k) unless k=0, in which case σkψ(u) = ψ(u).
NOTE: The reason for this is when the value ψ(η) was constructed, we skipped the value ηi and in doing this, we also skipped ui With σk, we are now creating a situation where each ui is shifted to ui+k so in this context, ui-k which we didn't skip before now becomes ui-k+k = ui.
(25) Therefore Mψ(η) ≡ ψ(u)ψ(η) not ≡ 0 (mod p) because ψ(u) not ≡ 0 (mod p).
NOTE: ψ(u) is a product of ep-e integers, none of them divisible by p. So in the definition of Mψ(η) all σkψ(u) = 0 so Mψ(η) not ≡ 0 (mod p) because ψ(u)ψ(η) not ≡ 0 (mod p).
(26) Further, M not ≡ 0 (mod p) since only ψ(η) not ≡ 0 (mod p).
(27) If u1, u2, ..., ue
(28) Since M not ≡ 0 (mod p), this implies σkψ(u) not ≡ 0 (mod p) for at least one k.
(29) That is, ∏(j - ui+k) not ≡ 0 (mod p) for at least one k, where i = 1, 2, ..., e and j assumes all values 1, 2, ..., p except ui.
NOTE: If this mapping did not occur then M ≡ 0 (mod p) which is contradicts our assumption that ui has satisfies all the equations of ui.
(30) This implies that ui ≡ ui+k (mod p) and the u's are a cyclic permutation of the u's as was to be shown.
(35) Finally, it remains to show that to say g(α) ≡ 0 (mod p) if and only if g(α) is divisible by all e of the prime divisors that have now been defined.
So, we need to show:
(a) Division by p implies division by all e of the prime divisors.
(b) Division by all e of the prime divisions implies division by p.
(36) Since p is divisible by all e of them, divisions by p implies division by all e of the prime divisors since congruence modulo a prime divisor is consistent with multiplication.
NOTE: See details on proposition 2 above if more information is needed.
(37) Conversely, it was shown in the proof of Theorem 3 above that divisibility of g(α) by the prime divisor of p corresponding to u1, u2, ..., ue is equivalent to g(α)ψ(η) ≡ 0 (mod p) where ψ(η) is the product of ep-e factors j - ηi in which j ≠ ui.
(38) Divisibility of g(α) by the prime divisor of p corresponding to uk+1, uk+2, ... , uk is equivalent to g(α)σ-kψ(η) ≡ 0 mod p because:
σ-kψ(η) = σ-k[ (i=1,e)∏ (j=1,p)∏ (j - ηi)/[(i=1,e)∏ (ui - ηi)]] =
= (i=1,e)∏ (j=1,p)∏ (j - ηi-k)/(i=1,e)∏(ui - ηi-k) =
= (i=1,e)∏ (j=1,p)∏ (j - ηi)/(i=1,e)∏(ui+k - ηi)
(39) That is, σ-kψ(η) is the ψ(η) that results from replacing u1, u2, ..., ue with u1+k, u2+k, ..., uk.
(40) Therefore, if g(α) is divisible by all e prime divisors of p, then g(α)σ-kψ(η) ≡ 0 (mod p) for all k = 0, 1, ..., e-1.
(41) The sum of these congruences gives g(α)*M ≡ 0 (mod p) which, because M ≠ 0 mod p implies g(α) ≡ 0 (mod p) as was to be shown.
QED
posted by Larry Freeman at 5:20 PM
0 Comments:
Post a Comment
<< Home