Cyclotomic Integers: Conjugations and the norm of a divisor

Definition 1: σ(p,ψ(η))

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

NOTE: In other words, if A is a prime divisor for a prime p, then σA divides g(α) implies that g(α)σψ(η) ≡ 0 (mod p).

Proposition 1:

Let σⁱ be a conjugation of cyclotomic integers, let g₁(α), g₂(α) be cyclotomic integers, and let A be a divisor.

Then, to say g₁(α) ≡ g₂(α) mod σⁱA is equivalent to saying σ^-ig₁(α) ≡ σ^-ig₂(α) mod A.

Proof:

(1) If A is a power of a prime divisor, say A = P^ν, and if σA divides g(α), then p^ν divides g(α)*σψ(η)^ν

By definition, we say that P^ν divides g(α) if g(α)ψ(η)^ν ≡ 0 (mod p^ν)

By σA divides g(α), we mean that g(α)σψ(η)^ν ≡ 0 (mod p^ν)

(2) This implies that p^ν divides σ^-1g(α)*ψ(η)^ν.

(a) g(α)σψ(η)^ν ≡ 0 (mod p^ν) means that g(α) is divisible by a conjugate to P which is σ¹P.

(b) This is the same as saying that σ^-1g(α) is divisible by P.

(3) Therefore it shows that A divides σ^-1g(α).

This follows since A dividing a cyclotomic integer is the same as showing σ^-1g(α)ψ(η)^ν ≡ 0 (mod p).

(4) If A,B are relatively prime and σ(AB) = σ(A)σ(B) divides g(α) then both σ(A) and σ(B) divide g(α), both A and B divide σ^-1g(α), and therefore, AB divides σ^-1(α).

This is the same reasoning as in step #3.

(5) This shows that, for any A, g(α) ≡ 0 (mod σA) implies σ^-1g(α) ≡ 0 (mod A).

(6) Then, g(α) ≡ 0 (mod σⁱA) implies σ^-1g(α) ≡ 0 (mod σ^i-1A), ...., σ^-ig(α) ≡ 0 (mod A).

(7) Conversely, σ^-ig(α) ≡ 0 (mod σ^λ-1-i(σⁱA)) implies g(α) = σ^-(λ-1)+iσ^-ig(α) ≡ 0 (mod σⁱA).

(8) Thus, (g₁ - g₂) ≡ 0 (mod σⁱA) is equivalent to σ^-i(g₁ - g₂) ≡ 0 (mod A), as was to be shown.

QED

Proposition 2:

If A is any divisor, there is a positive integer whose divisor is equal to the norm of A.

Proof:

(1) The norm of a divisor is defined to be:

A*σA*σ²A*...*σ^λ-2A.

(2) From this definition, it is easy to see that the norm of a product is the product of norms.

(3) So, that this theorem is proven if we can show that it is true for prime divisors.

(4) By the nature of the prime divisor, we know that it is divisor for an odd prime p so we are done.

QED

Cyclotomic Integers: Terminology

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.

Thereom 1:

Let A and B be divisors. If every cyclotomic integer divisible by A is also divisible by B, then A is divisible by B.

Proof:

(1) Let p₁, p₂, ..., p_n be the prime integers that are divisible by the prime divisors which divide A.

In other words, the p's are the prime factors of the norm of A. [This is explained later in the section on norms of divisors]

(2) Let A = A₁, A₂, ..., A_n be a decomposition of A as a product of divisors A_i such that A_i contains all prime divisors in A which divide p_i.

(3) Since a sufficiently high power of p₁, p₂, ... p_n is divisible by A it must, by assumption, be divisible by B.

NOTE: By assumption, we know that ∏ p_i is divisible by each prime divisor of A. If we raise this product to a sufficiently high power, then we know that each prime divisor of A will divide at the appropriate multiplicity. Without assuming a sufficiently high power, we cannot assume that this is the case.

(4) This shows that every prime divisor in B divides one of the p_i and therefore that B can be decomposed as a product B = B₁B₂*...*B_n in which B_i contains all prime divisors in B which divide p_i

Some of the B_i may be I since it may be possible that that a given p_i is not otherwise divisible by any of the divisors of B.

(5) Since the order of the p's is arbitrary, it will suffice to prove that B₁ divides A₁

We can then make the same argument for each B_i, A_i for p_i.

(6) If p₁ = λ, then A₁ = (α - 1)^μ for μ

(7) Then the cyclotomic integer (α - 1)^μ(p₂p₃*...*p_n)^ν is divisible by A for all sufficiently large ν

(8) Therefore it is also divisible by B for large ν.

(9) This implies because B₁ does not divide (p₂p₃*...*p_n)^ν at all, that B₁ divides the cyclotomic integer (α - 1)^μ

Again, since p₁ = λ by assumption, we know that the other p_i do not.

(10) Therfore B₁ divides the divisor of (α - 1)^μ, which is A₁.

(11) If p₁ ≠ λ, let f be the exponent of p₁ mod λ and let ψ be a cyclotomic integer made up of periods of length f which is divisible by one of the e = (λ - 1)/f prime divisors of p₁ with multiplicity 1 and is not divisible at all by the remaining e-1.

(12) Then one can form a product of conjugates of ψ, call it x, with the property that the divisor of x is A₁ times prime divisors which do not divide p₁.

(13) Now x(p₂p₃*...*p_n)^ν is divisible by A for large ν

(14) Therefore it is divisible by B₁.

(15) Since B₁ does not divide (p₂p₃*...*p_n)^ν at all, it follows that B₁ divides the divisor of x.

(16) Since the divisor of x is A₁ times a factor that contains none of the prime divisors of p₁ (and a fortiori none of the prime divisors of B₁) B₁ divides A₁ as was to be shown.

QED


Corollary:

If A and B are divisors and if the relation g₁(α) ≡ g₂(α) mod A" is equivalent to "g₁(α) ≡ g₂(α) mod B" (that is, one relation holds if and only if the other does), then A=B.

Proof:

This follows form the the Theorem above since if A divides B and B divides A then A = B.

QED

Cyclotomic Integers: 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.

Definition 1: Divisor of a nonzero cyclotomic integer

The divisor of a nonzero cyclotomic integer g(α) is a list, with multiplicities, of all the prime
divisors which divide g(α)

Definition 2: Empty list divisor

A divisor is any finite list of prime divisors. The empty list is considered to be a divisor. The empty list is a the divisor of the cyclotomic integer 1.

Definition 3: product of two divisors

The product of two divisors is the juxtaposition of the two lists counted with multiplicities.

Definition 4: Divisible by a divisor

A cyclotomic integer is said to be divisible by a given divisor if it can be written as a product of that divisor with another divisor. A cyclotomic integer is said to be divisible by a divisor if its divisor is divisible by that divisor and similarly a divisor is said to be divisible by a cyclotomic integer if it is divisible by the divisor of the cyclotomic integer.

NOTE: With these definitions, the fundamental theorem becomes the statement g(α) divides h(α) if and only if the divisor of g(α) divides the divisor of h(α)

Observation: The divisor of a product is the product of the divisors.

Observation: Since 0 is divisible by every nonzero cyclotomic integer, it is sometimes convenient to consider 0 to have the divisor which contains every prime divisor an infinite number of times.

Theorem 1:

Given a prime divisor of p ≠ λ there is a cyclotomic integer ψ(η) made up of periods of length f (the exponent of p mod λ) which is divisible exactly once by that prime divisor of p and which is not divisible by the remaining e-1 prime divisors of p. Consequently, a cyclotomic integer g(α) is divisible with multiplicity μ by the given prime divisor of p if and only if g(α)[σψ(η)]^μ[σ²ψ(η)]^μ*...*[σ^e-1ψ(η)]^μ is divisible by p^μ

Proof:

(1) Let ψ(η) correspond as before to a given prime divisor of p.

That is, let u₁, u₂, ..., u_e be the integers such that u_i - η_i is divisible by the given prime divisor and let ψ(η) be the product of ep-e factors j - η_i in which j ≠ u_i.

(2) Then ψ(η) is divisible by all e prime divisors of p except the given one.

(3) Let φ(η) = σψ(η) + σ²ψ(η) + ... + σ^e-1ψ(η).

(4) φ(η) is divisible by the given prime divisor of p (each term of the sum is divisible by it) but not divisible by the remaining e-1 prime divisors of p (for each of these all but one of the terms are divisible by it but that one is not divisible).

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

(5) If φ(η) is divisible with multiplicity exactly one by the given prime divisor of p, then ψ(η) = φ(η) has the required properties.

(6) If φ(η) is divisible with multiplicty greater than one, then set ψ(η) = φ(η) + p.

(7) Then, ψ(η) is not divisible by the e-1 prime divisors other than the given one (because if it were then φ(η) = ψ(η) - p would be), it is divisible by the given prime divisor of p (because φ(η) is), and it is not divisible with multiplicity greater than one (because if it were then p = ψ(η) - φ(η) would be).

(8) This completes the construction of ψ(η).

(9) The second statement of the theorem is an immediate consequence of the fundamental theorem.

QED

Theorem 2:

The cyclotomic integers called "prime" in the examples earlier are indeed prime. More generally, if p ≠ λ is a prime whose exponent mod λ is f and if g(α) is a cyclotomic integer whose norm is p^f then g(α) is prime. [If g(α) = g(η) is made up of periods of length f then the condition Ng(α) = p^f can also be stated in the form g(η)*σg(η)*...*σ^e-1g(η) = ± p.]

Proof:

(1) Let ν₁, ν₂, ...., ν_e be the exact multiplicities with which the prime divisors of p divide g(α).

(2) Then σg(α) is divisible with the multiplicities ν₂, ν₃, ...., ν_e, ν₁ exactly.

NOTE: This is true since σg(α) just shifts the prime divisors. (See Theorem 4, here)

(3) Then σ²g(α) is divisible with the multiplicities ν₃, ν₄, ...., ν₁, ν₂ exactly and so forth.

NOTE: Same reason as in step #2.

(4) Therefore, each prime divisor of p divides Ng(α) with multiplicity exactly (ν₁ + ν₂ + ... + ν_e)f.

NOTE: We know this since in the given, Ng(α) = p^f.

(5) If Ng(α) = p^f, then one ν_i must be 1 and the others 0.

NOTE: We know this since by our given (ν₁ + ν₂ + ... + ν_e)f= f since Ng(α) = p^f.

(6) Then, by the fundamental theorem, divisibility by g(α) coincides with divisibility by a prime divisor and it follows that g(α) is prime.

QED

Definition 5: greatest common divisor of p

Let a prime divisor of p be given and let ψ(η) be a cyclotomic integer as in the theorem above such that it is made up of periods of length f (the exponent of p mod λ) which is divisible just once by the prime divisor of p in question and not divisible by any of the remaining e-1 prime divisors of p. Then the given prime divisor wil be designated (p,ψ(η)). Since this divisor divides p and ψ(η), both with multiplicity exactly one, and no other prime divisor divides both, (p,ψ(η)) is the greatest common divisor of p and ψ(η).

Definition 6: Empty Divisor

The empty divisor which divides 1 will be denoted by I and an exponent of 0 on a divisor A will be defined to mean A⁰ = I.

Cyclotomic Integers: The Fundamental Theorem

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.

Theorem: The Fundamental Theorem for Cyclotomic Integers

Let λ be a given prime greater than 2 and let g(α), h(α) be nonzero cyclotomic integers built up from a λth root of unity α ≠ 1.

Then g(α) divides h(α) if and only if every prime divisor which divides g(α) also divides h(α) with multiplicity at least as great.

Proof:

(1) Let h(α) be divisible by g(α) such that h(α) = q(α)g(α)

(2) Certainly every prime divisor which divides g(α) also divides h(α) with multiplicity at least as great.

(3) Now g(α) divides h(α) if and only if Ng(α) = g(α)*g(α²)*...*g(α^λ-1) divides h(α)*g(α²)*...*g(α^λ-1)

(4) If every prime divisor which divides g(α) also divides h(α) with multiplicity at least as great then every prime divisor which divides Ng(α) also divides h(α)*g(α²)*...*g(α^λ-1) with the multiplicity at least as great.

(5) Since Ng(α) is an integer, from this point on we can assume that g(α) is a rational integer and that h(α) = h(α)*g(α²)*...*g(α^λ-1).

NOTE: The justification is that every cyclotomic integer can be made to depend on this equation where we show that every prime divisor that divides its norm necessarily divides the cyclotomic integer h(α)*g(α²)*...*g(α^λ-1)

(6) Now, we will proceed to prove this theorem for 3 cases:

Case I: g(α) is a prime integer p ≠ λ

Case II: g(α) is a prime integer p = λ

Case III: g(α) is not a prime integer

(7) Assume g(α) is a prime integer p ≠ λ

(8) From a previous result (See Theorem 4, here), we know that if h(α) is divisible by each of the e prime divisors of p, then h(α) is divisible by p.

(9) Assume g(α) is a prime integer p = λ

(10) From a previous result (See Proposition 2, here), we know that if h(α) is divisible by (α - 1)^{λ - 1}, then it is divisible by p = λ

(11) To prove case III, we will show that if the thereom is true for g₁(α) and g₂(α), then it is true for the product, g₁(α)*g₂(α)

(12) So, let us assume that all the prime divisors which divide g₁(α)*g₂(α) also divide h(α)

(13) Since all the prime divisors g₁(α) divide h(α), then it follows that g₁(α) divides h(α) and there exists h₁(α) such that:

h(α) = g₁(α)*h₁(α)

(14) By assumption, every divisor of g₂(α) divides h₁(α).

(15) Since we are assuming that the theorem holds true for g₂(α), then it follows that g₂(α) divides h₁(α) and there exists h₂(α) such that:

h₁(α) = g₂(α)*h₂(α)

(16) Therefore h(α) = g₁(α)g₂(α)h₂(α) we have shown that h(α) is divisible by g₁(α)g₂(α)

QED

Corollary 1.1: Unique Factorization is "saved"

If two cyclotomic integers g(α) and h(α) are divisible by exactly the same prime divisors with exactly the same multiplicities, then they differ only by a unit multiple, g(α) = unit * h(α)

Proof:

(1) By the fundamental theorem above, g(α) divides h(α) and h(α) divides g(α)

(2) Therefore, h(α)/g(α) and g(α)/h(α) are cyclotomic integers.

(3) Since their product is 1, they must both be units. (See here for more details if needed)

QED

NOTE: On the Fundamental Theorem and Unique Factorization.

The use of the fundamental theorem "saves" the property of unique factorization for primes as shown by the corollary but there is a price to pay. With the integers, we can arbitrarily organize any combination of primes and know that we have numbers. For prime divisors, this is no longer the case. For example, for λ = 23, there is no cyclotomic integer which is divisible once by one prime divisor of 47 and not divisible by any other prime divisor.

Cyclotomic integers: Multiplicities

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.

Definition 1: divisibility by a prime divisor

A cyclotomic integer g(α) is said to be divisible μ times by the prime divisor of p corresponding to u₁, u₂, ..., u_e if g(α)ψ(η)^μ is divisible by p^μ, where ψ(η) is the product of the ep-e factors j - η_i (i=1,2,.....,e; j=0,1,...,p-1; j ≠ u_i) that are not divisible by this prime divisor. It is said to be divisible exactly μ times by the prime divisor if it is divisible μ times but not divisible μ+1 times.

Proposition 1:

The notion of "divisible one time" coincides with the notion of "divisible" as defined earlier (see Definition 2, here). The notion of "divisible exactly zero times" coincides with "not divisible". The integer p is divisible exactly once; the integer 1 is not divisible at all. If g₁(α) and g₂(α) are both divisible μ times, then so is g₁(α) + g₂(α). If g₁(α) is divisible exactly μ times and g₂(α) is divisible exactly ν times then g₁(α)g₂(α) is divisible exactly μ + ν times. Finally, if g(α) ≠ 0 then there is a unique integer μ ≥ 0 such that g(α) is divisible exactly μ times.

Proof:

(1) g(α) is divisible by a prime divisor if and only if g(α)ψ(η) ≡ 0 (mod p) [See definition 2, here]

(2) This shows that g(α) is "divisible one time" if and only if g(α) is "divisible one time" [since g(α) is divisible "one time" if and only if g(α)ψ(η) ≡ 0 (mod p), see definition above]

(3) Since we know that ψ(η) not ≡ 0 (mod p) [See here if you need to review the construction of ψ(η)], we know that ψ(η)ψ(η) not ≡ 0 (mod p) and we know that pψ(η)ψ(η) not ≡ 0 (mod p²)

(4) Step #3 combined with step #2 shows that p is divisible exactly once.

(5) Because ψ(η) not ≡ 0 (mod p), we know that (1)ψ(η) not ≡ 0 (mod p) or in other words, the integer 1 is not divisible at all.

(6) The statement that g₁(α) + g₂(α) is divisible μ times whenever g₁(α), g₂(α) are, follows immediately from the definition.

(7) From the definition above, if g₁(α) is divisible exactly μ times then g₁(α)ψ(η)^μ+1 is divisible by p^μ but not by p^μ+1

(8) Therefore, φ₁(α) = p^-μg₁(η)ψ(η)^μ is a cyclotomic integer.

(9) Assume that φ₁(α) is divisible by one of the prime divisors.

(10) Since ψ(η) is divisible by the remaining e-1 prime divisors of p [since each remaining divisor is characterized by the formula ψ(η)σ^kψ(η) ≡ 0 (mod p), see Theorem 4 here for review], it follows that φ₁(α)ψ(η) is divisible by all e prime divisors of p.

(11) Hence, it would follow that p divides φ₁(α)ψ(η) [Note: this follows from Theorem 4 here]

(12) But then g₁(α) is divisible μ + 1 times by the prime divisor in question which contradicts the given so we can reject our assumption in step #9.

(13) Therefore φ₁(α) is not divisible by the prime divisor in question.

(14) Similarly, if g₂(α) is divisible exactly ν times, then φ₂ = p^-νg₂(α)ψ(η)^ν is a cyclotomic integer that is not divisible by the prime divisor in question.

(15) Therefore g₁(α)g₂(α)ψ(η)^μ+ν is divisible by p^{μ + ν} and the quotient is a product φ₁(α)φ₂(α) of two cyclotomic integers neither of which is divisible by the prime divisor in question.

(16) Because this prime divisor is prime, φ₁(α)φ₂(α) is not divisible by the prime divisor in question.

(17) Since ψ(η) is not divisible by this prime divisor [ψ(η)ψ(η) not ≡ 0 (mod p)] it follows that φ₁(α)φ₂(α)ψ(η) = g₁(α)g₂(α)ψ(η)^μ+ν+1p^-μ-ν is not divisible by the prime divisor of p and a fortiori that is not divisible by p. [Again, using Theoreom 4 from here]

(18) Therefore g₁(α)g₂(α)ψ(η)^μ+ν+1 is not divisible by p^{μ + ν + 1} and g₁(α)g₂(α) is divisible with multiplicity exactly μ + ν as was to be shown.

(19) Let g(α) be a cyclotomic integer such that g(α) ≠ 0.

(20) If there is an integer k greater than 0 such that g(α) is not divisible k times by the prime divisor of p in question, then directly from the definition, there must be at least one integer μ such that 0 ≤ μ is less than k such that g(α) is divisible exactly μ times.

(21) As was seen above, this implies that g(α)ψ(η)^μ/p^μ is not divisible at all.

(22) Therefore, for any j ≥ 0, g(α)ψ(η)^μ+j/p^μ is not divisible at all.

(23) Consequently, g(α) is not divisible with multiplicity μ + j for j greater than 0.

(24) In particular, g(α) is not divisible with multiplicity m whenever m is greater than k.

(25) To prove the last statement of the proposition, it will suffice to prove that there is an integer k such that g(α) is not divisible k times, because then the exact multiplicity μ with which g(α) is divisible is uniquely determined as the largest integer μ such that g(α) is not divisible μ times.

(26) To this end, note that if g(α) is divisible k times, so is Ng(α).

(27) Let Ng(α) = pⁿq where n ≥ 0 and q is not divisible by p.

(28) Then, Ng(α) is divisible exactly n times and cannot therefore be divisible k times whenever k is greater than n and the proof is complete.

QED

Definition 2: Multiplicity of a prime divisor

A prime divisor in the arithmetic of cyclotomic integers (for a fixed prime λ greater than 2) is either (a) one of the e prime divisors of some prime p ≠ λ that have been defined above or (b) the prime divisor α - 1 of λ. The prime divisors of the first type are described by giving a prime p ≠ λ and the integers u₁, u₂, ..., u_e. Given a cyclotomic integer g(α) ≠ 0 and a prime divisor there is a multiplicity μ ≥ 0 with which g(α) is divisible by the prime divisor. For prime divisors of the first type this multiplicity is defined to be the exact multiplicity with which g(α) is divisible by the prime divisor in the sense just defined above. For the single prime divisor of the second type it is defined to be the number of times that α - 1 divides g(α)

Proposition 2:

Congruence mod α - 1 is reflexive, symmetric, transitive, and consistent with addition and multiplication. Moreover, α - 1 is prime; that is, g₁(α)g₂(α) ≡ 0 (mod α - 1) implies that either g₁(α) ≡ 0 or g₂(α) ≡ 0 (mod α - 1). An integer is divisible by α - 1 if and only if it is divisible by λ. The multiplicity with which g(α) ≠ 0 is divisible by α - 1 is well defined; that is, there is a μ ≥ 0 such that (α - 1)^μ divides g(α) but (α - 1)^μ+1 does not. If α - 1 divides both g₁(α) and g₂(α) with multiplicity at least μ, then it divides g₁(α) + g₂(α) with multiplicity at least μ. If α - 1 divides g₁(α) with multiplicity exactly μ and g₂(α) with multiplicity exactly ν then it divides g₁(α)g₂(α) with multiplicity exactly μ + ν. Finally, λ divides g(α) if and only if α - 1 divides g(α) with multiplicity at least λ - 1.

Proof:

(1) α - 1 divides g(α) if and only if g(1) ≡ 0 (mod λ) since:

(a) N(α - 1) = λ [See Lemma 6 here for details.]

(b) Since α - 1 divides g(α) implies N(α-1) divides Ng(α), we know that this is only the case if Ng(α) is divisible by λ which means that if g(α) is an integer, that g(α) must be divisible by λ.

(c) Assume α - 1 divides g(α) so that g(α) ≡ 0 (mod α -1 )

(d) Then g(1) ≡ 0 (mod α - 1) since α ≡ 1 (mod α - 1) so any equation with α is congruent to the same equation with 1.

(e) Then step d implies that α - 1 divides g(1).

(f) But then λ must divide g(1) since N(α - 1) divides Ng(1) and the only way that this can happen is if g(1) is divisible by λ

(g) Assume g(1) ≡ 0 (mod λ)

(h) Then g(1) ≡ 0 (mod α - 1) since (α - 1)(α² - 1)*...*(α^λ-1 - 1) = λ

(2) We know that α - 1 is prime since N(α - 1)= λ which is a prime.

(3) All statements but the last follow from the same reasoning as the details behind Theorem 1.

(4) The last statement follows from the fact that λ = (α - 1)(α² - 1) * ... *(α^λ-1 - 1) = (α - 1)^λ-1 * unit

QED

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: x^p - x ≡ (x-1)(x-2)*...*(x-p) ≡ 0 (mod p)

Proof:

(1) Fermat's Little Theorem gives us:

x^p-1 ≡ 1 (mod p)

So that:

p divides x^p-1 - 1

So that:

x(x^p-1 - 1) = x^p - 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:

x^p - x ≡ (x-1)(x-2)*...*(x-p) ≡ 0 (mod p)

QED

Proposition 2: Given λ, p, f, e, there exist integers u₁, u₂, ..., u_e with the property that equation satisfied by the periods η of length f is satisfied as a congruence modulo p by the integers u_i.

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) ≡ η_i^p - η_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 u_i - η_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, u_i = j such that j - η_i is divisible by p.

(9) Then (j - η_i)ψ(η) ≡ 0 ≡ (u_i - η_i)ψ(η) (mod p.)

(10) Since u_i = j, we also have:

(j - u_i)ψ(η) ≡ 0 (mod p)

(11) Further, there is only 1 integer between 1 and p for u_i - η_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 u_i - η_i

QED

Corollary 2.1:

In Proposition 2 above, u_i are such that if F(η₁, η₂, ... , η_e) is any polynomial expression in the η's with integer coefficients and if the cyclotomic integer F(η₁, η₂, ..., η_e) is 0, then the integer F(u₁, u₂, ..., u_e) obtained by substituting u_i in place of η_i (i = 1, 2, 3, ..., e) satisfies F(u₁, u₂, ..., u_e) ≡ 0 (mod p).

Proof:

(1) From, the Proposition:

η_iψ(η) ≡ u_iψ(η) (mod p) for i = 1,2, ..., e. [Since, u_i - η_i ≡ 0 (mod p) → ψ(η)[u_i - η_i] ≡ u_iψ(η) - η_iψ(η) ≡ 0 (mod p)]

(2) Therefore F(η₁, η₂, ..., η_e)ψ(η) ≡ F(u₁, u₂, ..., u_e)ψ(η) mod p for any polynomial F(η₁, η₂, ..., η_e) in periods since the congruence mod p is consistent with addition and multiplication (see here for details)

(3) If F(η₁, η₂, ..., η_e) = 0, then F(u₁, u₂, ..., u_e)ψ(η) ≡ 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(u₁, u₂, ..., u_e) ≡ 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 u_i, p is congruent to 0, and 1 is not congruent to 0. Finally, the number of incongruent elements is exactly p^f

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 ≠ u_i is not divisible by p.

There exist u₁, u₂, ... , u_e 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 ≡ u_i.

(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 ~ u_i, p ~ 0, and 1 not ~ 0.

(7) Since every cyclotomic integer g(α) can be written in the form g₁(η)α^f-1 + g₂(η)α^f-2 + ... + g_f(η) [See Lemma 1, here], it follows that g(α) ~ a₁α^f-1 + a₂α^f-2 + ... + a_f where 0 ≤ a_i ≤ p-1.

(8) Therefore, there are at most p^f 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 ψ₁(α), ψ₂(α) such that ψ₁(α)ψ₂(α) ~ 0 but ψ₁(α) not ~ 0 and ψ₂(α) not ~ 0.

(11) We can define another congruence relation ~₂ such that:

g(α) ~₂ φ(α) if and only if g(α)ψ₁(α) ~ φ(α)ψ₁(α)

(12) We can see that ~₂ is reflexive, symmetric, transitive, and consistent with addition and multiplication with η_i ~₂ u_i, p ~₂ 0, and 1 not ~₂ 0.

(13) We can also see that this relation has fewer incongruent integers from ~ since:

ψ₂(α) ~₂ 0 but ψ₂(α) not ~ 0 (by step #10 above)

(14) So ~₂, we see has p^f-1 incongruent cyclotomic integers; that is, it has at least 1 less than ~.

(15) Now, if ~₂ is not prime, then we repeat the steps #10 thru #14, to derive a congruence relation ~₃ with at most p^f-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):

a₀ + a₁α + ... + a_λ-1α^λ-1

(d) We can further assume that all a_i are between 0 and p-1 since if a_i is greater than p, then there exists a' such that a_i ≡ a' (mod p) where a' is less than p and further if a_i ≡ a' (mod p), then a_iψ(η) ≡ a'ψ(η) (mod p).

(e) But if all a_i 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(α)α², ..., 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 p^f 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:

p^x ≡ 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(α) ~ a₁α^f-1 + a₂α^f-2 + ... + a_f and φ(α) ~ b₁α^f-1 + b₂α^f-2 + ... + b_f where a_i, b_i are the integers 0 ≤ a_i ≤ p-1 and 0 ≤ b_i ≤ p-1. [See step #7 if more details are needed]

(23) By the transitivity of ~ and the fact that ~ has p^f incongruent cyclotomic integers, g(α) ~ φ(α) if and only if the cyclotomic integers a₁α^f-1 + a₂α^f-2 + ... + a_f and b₁α^f-1 + b₂α^f-2 + ... + b_f 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 u₁, u₂, ..., u_e.

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 u₁, u₂, ..., u_e

Theorem 4:

For a given λ, p, f, e, let u₁, u₂, ..., u_e and u₁, u₂, ..., u_e 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 u₁, u₂, ..., u_e coincides with congruence modulo the prime divisor of p corresponding to u_1+k, u_2+k, ..., u_k where, as usual, u_j = u_j+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 u₁, u₂, ..., u_e be a set of integers yielded by the construction in the proof of the proposition 2 above.

(2) Let u₁, u₂, ..., u_e 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:

η₁, η₂, ..., η_e

where each period consists of the following:

(a) η₁ = α + σ^eα + σ^2eα + ... + σ^λ-1-eα

(b) η_i+1 = ση_i

(4) Let us consider now the product of η₁ with an arbitrary period η_i:

η₁η_i = c₀ + c₁η₁ + c₂η₂ + ... + c_eη_e

where c_i 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 η₁η_i is:

(f)(f) = f² = c₀(1) + c₁(f) + ... + c_e(f)

NOTE: We can do this since c_i 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, c₀ ≠ 0 only if at least one term α^μ of η_i is the inverse of the term α^-μ in η₁. [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 η₁ [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 c₀ = f for this one value of i (as mentioned in step #8) and c₀=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 c₀ = f giving us:

c₁ + c₂ + ... + c_e = f[c₁ + c₂ + ... + c_e]/f = (f² - f)/f = f-1.

For all others c₀ = 0 giving us:

c₁ + c₂ + ... + c_e = f[c₁ + c₂ + ... + c_e]/f = f²/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:

η₁η_i + η₂η_i+1 + ... + η_eη_i-1 = η1η_i + σ(η₁η_i) + ... + σ^e-1(η₁η_i)

(11) Using the result in step #10 and combining it with the result in step #6 gives us:

η1η_i + σ(η₁η_i) + ... + σ^e-1(η₁η_i) =

= c₀ + c₁η₁ + c₂η₂ + ... + c_eη_e + σ(c₀ + c₁η₁ + c₂η₂ + ... + c_eη_e) + ... + σ^e-1(c₀ + c₁η₁ + c₂η₂ + ... + c_eη_e) =

= ec₀ + c₁(η₁ + η₂ + ... + η_e) + ... + c_e(η_e + η₁ + ... + η_e-1) =

= ec₀ + (c₁ + c₂ + ... + c_e)(η_e + η₁ + ... + η_e-1)

(12) Remembering that η₁ + η₂ + ... + η_e = α + α² + ... + α^λ-1 gives us (Lemma 2, here):

η₁ + η₂ + ... + η_e = -1.

(13) Applying the result in step #12 to step #11 gives us:

η₁η_i + η₂η_i+1 + ... + η_eη_i-1 = ec₀ - (c₁ + c₂ + ... + c_e)

(14) So that applying step # 9 gives us:

η₁η_i + η₂η_i+1 + ... + η_eη_i-1 =

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 + η₁η_f + η₂η_j+1 + ... + η_eη_j-1 = λ (in one case) or 0 (in all other cases).

(16) Now, using the fact that η_i ≡ u_i (mod p) gives us:

f + u₁u_i + u₂u_i+1 + ... + u_eu_i-1 not ≡ 0 (mod p) in 1 case and ≡ 0 (mod p) in all other cases.

(17) If there were a k such that u_i ≡ u_i+k (mod p) for all i then:

f + u₁u_i + u₂u_i+1 + ... + u_eu_i-1 ≡ f + u₁u_i+k + u₂u_i+k+1 + ... + u_eu_i+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 u_i+e = u_e since periods are unchanged by σ^e.

(19) This proves that the e cyclic permutations of the u's are all distinct. That is, if u_i ≡ u_i+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α² + ... + cα^λ-1. Since α + α² + ... + α^λ-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 η₁ = u₁, η₂ = u₂, ..., η_e = u_e in the result.

(23) In short, σ^kψ(u) = ∏(j - u_i+k) where i = 1, 2, ..., e and j ranges over all integers from 1 to p except u_i.

NOTE: This is clear based on the definition of ψ(u) = ∏(j - u_i)

(24) By what was just shown, σ^kψ(u) contains a factor of 0 (namely a factor u_i+k -u_i+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 u_i With σ^k, we are now creating a situation where each u_i is shifted to u_i+k so in this context, u_i-k which we didn't skip before now becomes u_i-k+k = u_i.

(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 u₁, u₂, ..., u_e satisfy the condition of the proposition, then M ≡ ψ(u) + σψ(u) + ... + σ^e-1ψ(u) mod p since they follow the same relations as u_i.

(28) Since M not ≡ 0 (mod p), this implies σ^kψ(u) not ≡ 0 (mod p) for at least one k.

(29) That is, ∏(j - u_i+k) not ≡ 0 (mod p) for at least one k, where i = 1, 2, ..., e and j assumes all values 1, 2, ..., p except u_i.

NOTE: If this mapping did not occur then M ≡ 0 (mod p) which is contradicts our assumption that u_i has satisfies all the equations of u_i.

(30) This implies that u_i ≡ u_i+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 u₁, u₂, ..., u_e is equivalent to g(α)ψ(η) ≡ 0 (mod p) where ψ(η) is the product of ep-e factors j - η_i in which j ≠ u_i.

(38) Divisibility of g(α) by the prime divisor of p corresponding to u_k+1, u_k+2, ... , u_k is equivalent to g(α)σ^-kψ(η) ≡ 0 mod p because:

σ^-kψ(η) = σ^-k[ (i=1,e)∏ (j=1,p)∏ (j - η_i)/[(i=1,e)∏ (u_i - η_i)]] =

= (i=1,e)∏ (j=1,p)∏ (j - η_i-k)/(i=1,e)∏(u_i - η_i-k) =

= (i=1,e)∏ (j=1,p)∏ (j - η_i)/(i=1,e)∏(u_i+k - η_i)

(39) That is, σ^-kψ(η) is the ψ(η) that results from replacing u₁, u₂, ..., u_e with u_1+k, u_2+k, ..., u_k.

(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