Cyclotomic Integers: Divisibility Test

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

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

Proof:

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

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

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

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

QED

Lemma 2: Every cyclotomic integer g(α) is congruent mod h(α) to a cyclotomic integer of the form a₁α^f-1 + a₂α^f-2 + ... + a_f where a_i are positive integers less than a prime integer p.

Proof:

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

g(α) = g₁(η)α^f-1 + g₂(η)α^f-2 + ... + g_f(η)

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

(2) Each cyclotomic integer g_i(η) is congruent mod h(α) to an integer g_i(u) where g_i(u) denotes the integer obtained by substituting u₁ for η₁, u₂ for η₂, 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 g_i(u) is between 0 and p-1 since:

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

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

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

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

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

g(α) = g₁(η)α^f-1 + g₂(η)α^f-2 + ... + g_f(η) ≡ g₁(u)α^f-1 + g₂(u)α^f-2 + ... + g_f(u) ≡

≡ a₁α^f-1 + a₂α^f-2 + ... + a_f (mod h(α))

where a_i is between 0 and p-1.

QED

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

Proof:

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

g(α) ≡ a₁α^f-1 + a₂α^f-2 + ... + a_f (mod h(α)) where a_i 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^f 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: Z₉ is an additive group

Z₉ = { 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 ∈ Z₉, 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 λ, αⁱ ≠ 1. [See here for review of roots of unity]

(2) All cyclotomic integers based on λ can be put into this form:

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

where a_i are all integers [See Lemma 1 here]

(3) Since we are talking about values modulo p, we can assume that a_i 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):

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

(e) But if all a_i 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 p^f ≡ 1 (mod λ)

Lemma 5: Let S be the set of cyclotomic integers of the form a₁α^f-1 + a₂α^f-2 + ... + a_f where a_i are positive integers less than p.

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

Proof:

(1) The number of incongruent elements mod h(α) is a power of p, say pⁿ 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, α, α², ..., α^λ=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 αⁱ - α^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 α, α², ..., α^λ =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 ψ(α)α, ψ(α)α², ..., ψ(α)α^λ = ψ(α) are all nonzero mod h(α) [because h(α) is prime] and distinct mod h(α) [because ψ(α)α^j ≡ ψ(α)α^k would imply α^j ≡ α^k) and distinct from α, α², ..., α^λ (because ψ(α)α^j ≡ αⁱ 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 pⁿ - 1.

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

mλ = pⁿ - 1.

(6) This gives us that:

pⁿ ≡ 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 pⁿ is greater than λ + 1. ]

(8) Thus, the number of pⁿ of incongruent elements mod h(α) is at least p^f.

QED

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

Proof:

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

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

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

QED

Cyclotomic Integers: Generalizing Periods

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

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

g(α) = g₁(η)α^f-1 + g₂(η)α^f-2 + ... + g_f(η)

where g₁(η), g₂(η), ..., g_f(η) are cyclotomic integers made up of periods of length f. [See Definition 2 here for review of cyclotomic integers made up of periods of length f]

Proof:

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

g(α) = a₀ + a₁α + a₂α² + ... + a_f-1α^f-1

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

Let g_f(η) = a₀ + (0)η₀ + (0)η₁ + ... + (0)η_e-1

Let g_f-1(η) = a₁ + (0)η₀ + (0)η₁ + ... + (0)η_e-1

and so on until:

Let g₁(η) = a_f-1 + (0)η₀ + (0)η₁ + ... + (0)η_e-1

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

g(α) = g₁(η)α^f-1 + g₂(η)α^f-2 + ... + g_f(η)

QED

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

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

Proof:

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

g(α) = g₁(η)α^f-1 + g₂(η)α^f-2 + ... + g_f(η)

h(α) = h₁(η)α^f-1 + h₂(η)α^f-2 + ... + h_f(η)

j(α) = j₁(η)α^f-1 + j₂(η)α^f-2 + ... + j_f(η)

where where g₁(η), g₂(η), ..., g_f(η), h_i(η), j_i(η) are cyclotomic integers made up of periods of length f.

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

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

For each g_i(η), h_i(η), we have:

g_i(η) = a₀ + a₁η₀ + ... + a_fη_f-1

h_i(η) = b₀ + b₁η₀ + ... + b_fη_f-1

And we can define s_i(η) such that:

s_i(η) = (a₀ + b₀) + (a₁ + b₁)η₀ + ... + (a_f + b_f)η_f-1

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

g(α)h(α) = [g₁(η)α^f-1 + g₂(η)α^f-2 + ... + g_f(η)][h₁(η)α^f-1 + h₂(η)α^f-2 + ... + h_f(η)] =

= [g₁(η)α^f-1][h₁(η)α^f-1] + ... + [ g_f(η) ][h_f(η)]

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

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

QED

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

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

where φ₁(η), φ₂(η), ..., φ_f(η) are cyclotomic integers made up of periods of length f.

Proof:

(1) Let λ be an odd prime.

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

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

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



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

For review of σ notation, see here.

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

p(x) = x^f + φ₁(η)x^f-1 + ... + φ_f-(η)x + φ_f(η)

where φ(η) is a cyclotomic integer.

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

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

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

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

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

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

p(x) = x^f + φ₁(η)x^f-1 + ... + φ_f-(η)x + φ_f(η)

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

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

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

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

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

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

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

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

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

(9) So putting this all together gives us:

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

QED

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

g(α) = g₁(η)α^f-1 + g₂(η)α^f-2 + ... + g_f(η)

where g₁(η), g₂(η), ..., g_f(η) are cyclotomic integers made up of periods of length f.

Proof:

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

g(α) = a₀ + a₁α + a₂α² + ... + a_λ-1α^λ-1

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

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

g(x) = a₀ + a₁x + a₂x² + ... + a_λ-1

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

p(x) = x^f + φ₁(η)x^f-1 + ... + φ_f-1(η)x + φ_f(η)

where φ(η) is a cyclotomic integer.

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

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

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

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

α^f = -φ₁(η)x^f-1 - ... - φ_f-1(η)x - φ_f(η)

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

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

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

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

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

q(x) = q₁(x)(x^f) + r(x)

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

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

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

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

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

QED

Example:

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

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

Let g(α) = α⁴ + 2α³ + 3α² + 4α + 5

We note that:

2¹ ≡ 2 (mod 5)
2² ≡ 4 (mod 5)
2³ ≡ 3 (mod 5)
2⁴ ≡ 1 (mod 5)

In this case,

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

Now σ^eα = α^γ2 = α⁴

σ^2eα = α^γ4 = α

So,

p(x) = x² - x(α⁴ + α) + α⁵ = x² - x(α⁴ + α) + 1.

We see that p(α) = 0 since:

p(α) = α² - α(α⁴ + α) + 1 = α² - 1 + α² + 1 = 0

So that:

α² = α(α⁴ + α) - 1

Let g(x) = x⁴ + 2x³ + 3x² + 4x+ 5

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

with:
η₀ = α⁴ + α

η₁ = α³ + α²

(η₀)² = α³ + α² + 2.

(η₀)(η₁) = η₀ + η₁

Using the Division Algorithm for polynomials, we see that:

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

where:

q(x) = x² + 2x + 3

r(x) = 4x + 5

x² = x(α⁴ + α) - 1

and:

q(α) = [α(α⁴ + α) - 1] + [2α + 3] = α(η₀ + 2) + (2)

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

α² = [α(α⁴ + α) - 1] = α(η₀) + (-1)

Then

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

= α²(η0² + 2η₀) + α(2η₀) + α(-η₀ - 2) -2 + α(4) + (5) =

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

= α(4η₀ + 3η₁+ 4) + (-3η₁ + 1)

So, let:

g₁(η) = 4η₀ + 3η₁ + 4

g₂(η) = -3η₁ + 1

And finally, this gives us:

g(α) = g₁(η)α + g₂(η)

Cyclotomic Integers: More on cyclotomic periods

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


Lemma 1: 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 p^f ≡ 1 (mod λ)

(6) We know that f divides λ -1 since:

(a) p^λ-1 ≡ 1 (mod λ) from Fermat's Little Theorem (since p,λ are distinct primes)

(b) From a previous result (see Lemma 2 here), we know if f is the least positive integer, then it must divide λ-1.

(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:

τ = (σ₁^e)(σ₂^e)...(σ_k'^e)

and therefore:

τg(α) =(σ₁^e)(σ₂^e)...(σ_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 p^f ≡ 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


Lemma 2: Let h(α) be a prime cyclotomic integer. For any cyclotomic integer g(α) made up of periods of length f, there exists an integer u such that g(α) ≡ u (mod h(α))

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) (mod p)

(4) Let x = g(α)

(5) Then:

g(α)^p - g(α) ≡ [g(α) - 1][g(α) - 2]*...*[g(α) - p] (mod p)

(6) 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)

(7) Since h(α) divides p, then we have:

g(α^p) - g(α) ≡ [g(α) - 1][g(α) - 2]*...*[g(α) - p] (mod h(α))

(8) Now, since g(α) is made up of periods of length f, we know that g(α^p) = g(α) [See Lemma 1 above]

So that:

g(α^p) - g(α) = 0 ≡ 0 (mod h(α))

(9) This gives:

[g(α) - 1][g(α) - 2][g(α) - 3]*...*[g(α)-p] ≡ 0 (mod h(α))

(10) Since h(α) is a prime cyclotomic integer, one of these values must be divisible by h(α) [By the definition of a cyclotomic prime, see here]

(11) So there exists an integer u such that h(α) divides g(α) - u

Which means that:

g(α) ≡ u (mod h(α))

QED

Corollary 2.1: Let h(α) be a prime cyclotomic integer. Let η_i be a period of length f. Then, there exists an integer u_i such that η_i ≡ u_i (mod h(α))

Proof:

(1) Each period η_i can be thought of as a cyclotomic integer made up of periods of length f:

g(α) = (0)η₀ + ... + (1)η_i + ... + (0)η_e-1 = η_i

(2) From Lemma 2 above, we know that there exists an integer u_i such that g(α) ≡ u_i (mod h(α))

(3) So, we see that for each η_i, there exists u_i such that:

η_i ≡ u_i (mod h(α))

QED

Cyclotomic Integers: g(α)p ≡ g(αp) (mod p)

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: if p is a prime, then (x + y)^p ≡ x^p + y^p

Proof:

(1) Using the Binomial Theorem, we know that:




(2) Now, this means that each of the coefficients is equal to:



(3) But since p is a prime, p divides all coefficients.

For all values where k is between 1 and p-1, p, as a prime, will not be divisible by either k! or by (p-k)!.

(4) This means that p will divides (x + y)^p - x^p - y^p.

QED

Lemma 2: x^p ≡ x (mod p)

Proof:

(1) x^p - x = x(x^p-1 - 1)

(2) if gcd(x,p)=1, then by Fermat's Little Theorem, x^p-1 ≡ 1 (mod p) so p divides x^p-1-1.

(3) if p divides x, then of course p divides x(x^p-1-1)

QED

Lemma 3: g(α) ≡ g(α^p) mod p

Proof:

(1) Let g(α) = a₀ + a₁α + ... + α_λ-1α^λ-1.

(2) Then g(α)^p = (a₀ + [a₁α + ... + α_λ-1α^λ-1])^p

(3) Now using Lemma 1 above, we can break #2 out in the following ways:

(a₀ + [a₁α + ... + α_λ-1α^λ-1])^p ≡ (a₀)^p + (a₁α + [... + α_λ-1α^λ-1])^p (mod p).

(4) We could keep breaking out each element until we get:

(a₀ + [a₁α + ... + α_λ-1α^λ-1])^p ≡ (a₀)^p + (a₁α)^p + ... + (a_λ-1α^λ-1)^p (mod p)

(5) Now for each coefficient a_i, using Lemma 2 above, we have:

a_i^p ≡ a_i (mod p)

So this gives us:

(a₀)^p + (a₁α)^p + ... + (a_λ-1α^λ-1)^p ≡ a₀ + a₁α^p + ... + a_λ-1(α^λ-1)^p (mod p)

(6) And we are done since this shows that:

g(α)^p ≡ g(α^p) (mod p)

QED

Cyclotomic Integers: Periods

In today's blog, I will review the concept of periods for cyclotomic integers 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.

I will continue to use Edward's σg(α) notation that I reviewed in a previous blog.

Lemma 1:

Let e be a factor of λ - 1 where λ is an odd prime and α is a primitive root of unity where α^λ = 1.

Then, for a given cyclotomic integer g(α) there exists a cyclotomic integer G(α) such that:

Ng(α) = G(α)*σG(α)*...*σ^e-1G(α)

Proof:

(1) Let G(α) = g(α)*σ^eg(α)*σ^2eg(α)*...*σ^-eg(α) where σ^-e denotes σ^λ-1-e

(2) With this definition we can see that:

G(α) = g(α)*g(α^γe)*g(α^γ2e)*...*g(α^γ(λ-1-e))

σG(α) = g(α^γ)*g(α^γ(e+1))*g(α^γ2e+1)*...*g(α^γλ-e)

...

σ^e-1G(α) = g(α^γ(e-1))*g(α^γ(2e-1))*...*g(α^γ(λ-2))

(3) Putting this all together, we see that:

Ng(α) = g(α)*g(α^γ)*g(α^γ*γ)*...*g(α^γ(λ-2))

(4) Since γ is a primitive root mod λ, we know that (3) is the same as:

Ng(α) = g(α)*g(α²)*g(α³)*..*g(α^λ-1)

QED

Example 1: λ = 13, γ = 2, and e = 4

In this case, Ng(α) = G(α)G(α)G(α⁴)G(α⁸)

Each term G(α) = g(α)*g(α²⁴)*g(α^22*4) = g(α)*g(α³)*g(α⁹)

Since:

2 ≡ 2 (mod 13)
2² ≡ 4 (mod 13)
2³ ≡ 8 (mod 13)
2⁴ ≡ 16 ≡ 3 (mod 13)
2⁵ ≡ 32 ≡ 6 (mod 13)
2⁶ ≡ 64 ≡ 12 (mod 13)
2⁷ ≡ 128 ≡ 11 (mod 13)
2⁸ ≡ 256 ≡ 9 (mod 13)
2⁹ ≡ 512 ≡ 5 (mod 13)
2¹⁰ ≡ 1024 ≡ 10 (mod 13)
2¹¹ ≡ 2048 ≡ 7 (mod 13)
2¹² ≡ 4096 ≡ 1 (mod 13)

Corollary 1.1: σ^eG(α) = G(α)

Proof:

(1) G(α) = g(α)*g(α^γe)*g(α^γ2e)*...*g(α^γ(λ-1-e))

(2) And we find that:

σ^eG(α) = g(α^γe)*g(α^γ2e)*g(α^γ3e)*...*g(α^γλ-1)

(3) And since γ^λ-1 ≡ 1 (mod λ) (By Fermat's Little Theorem), we see that the result in step #2 is the same as the result in step #1.

QED

Corollary 1.2: σ^eG(α) = G(α) implies that there exists a set of e cyclotomic integers: η₀, η₁, ... η_e-1 such that:

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

(b) η_i+1 = ση_i

(c) G(α) = a₀ + a₁η₀ + a₂η₁ + ... + a_eη_e-1 where a_i are integers.

Proof:

(1) σ^eG(α) = G(α)

(2) Since G(α) is a cyclotomic integer, we know that (see Lemma 1 here):

G(α) = a₀ + a₁α + ... + a_λ-1α^λ-1

(3) Now, (#1) implies that the coefficient for any α^j, α^j = σ^eα^j

(4) In order for #3 to be true, then G(α) must have the following form:

G(α) = a₀ + a₁(α + σ^eα + σ^2eα + ... + σ^λ-1-e) + a₂(σα + σσ^eα + ...) + ... + a_e(σ^e-1α + σ^e-1σ^eα + ...)

The reason being that each time all the values G(α) shifts by e, the new value must also have had the same coefficient and further, all new resulting values must be the same as values that existed before the shift. For each coefficient, the set of possible α^j values must be closed.

(5) Now, we can define η₀ in the following way:

η₀ = α + σ^eα + σ^2eα + ... + σ^λ-1-e

(6) We can likewise define η_i+1 as:

η_i+1 = ση_i

(7) Putting (5) and (6) into the equation in step #4 gives us:

G(α) = a₀ + a₁η₀ + ... + a_eη_e-1

QED


Definition 1: Cyclotomic Period

Let λ be a prime integer. Let α be a primitive root of unity such that α^λ=1. Let γ be a primitive root modulo λ. Let e be a factor of λ - 1.

Let G(α) = g(α)*g(α^γe)*g(α^γ2e)*...*g(α^γ(λ-1-e))

Then there exists a set of e cyclotomic integers: η₀, η₁, ... η_e-1 such that:

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

(b) η_i+1 = ση_i

(c) G(α) = a₀ + a₁η₀ + a₂η₁ + ... + a_eη_e-1 where a_i are integers.

The cyclotomic integers η₀, η₁, ... η_e-1 that meet conditions (a), (b), and (c) are called cyclotomic periods.

Note:

As a convention, η_e = η₀ and η_-1 = η_e-1. So one can think of η_i as an ever repeating pattern of e values such that η_i+1 = ση_i

In this way, η_i is defined for all integers i.

Example 1: period for λ = 13, μ = 2, γ = 4

In this case, the cyclotomic periods are:

η₀ = α + σ⁴α + σ⁸α = α + α³ + α⁹

η₁ = σα + σα³ + σα⁹ = α² + α⁶ + α⁵

η₂ = σ²α + σ²α³ + σ²α⁹ = α⁴ + α¹² + α¹⁰

η₃ = σ³α + σ³α³ + σ³α⁹ = α⁸ + α¹¹ + α⁷

Lemma 2: σ^eη_i = η_i

Proof:

(1) For Case 0, this is given by the note in definition 1 above.

σ^eη₀ = η_e = η₀

(2) Let's assume that this is true up to i so that:

σ^eη_i = η_i where 0 ≤ i.

(3) Then, this is also true for η_i+1 since:

σ^e(η_i+1) = σ^e(ση_{i) [From Definition 1 above]}

Now σ^eσ = σ^e+1 = σσ^e

So that we get:

σ^eη_i+1 = σ(σ^eη_i)

By assumption at step #2, σ^eη_i = η_i

So that we end up with:

σ^eη_i+1 = ση_i = η_i+1

(4) So, by the principle of induction, we are done.

QED


Lemma 3: Each period η consists of (λ-1)/e terms.

Proof:

(1) Let f = (λ - 1)/e.

(2) σ^efα = σ^λ-1α = α

(3) σ^{(λ - 1 - e)}α = σ^e(f-1)α = (σ^e)^f-1α

(4) So we can see that each term in α + σ^eα + σ^2eα + ... + σ^λ-1-eα is σⁱα where i is 0*e, 1*e, 2*e, ... , (f-1)*e.

QED

Definition 2: Made up of periods of length f

A cyclotomic integer is made up of periods of length f if it can be put in the form:

a₀ + a₁η₁ + a₂η₂ + ... + a_eη_e

where a_i are integers and η_i are periods of length f.

Lemma 4: A cyclotomic integer g(α) is made up of periods of length if and only if σ^eg(α) = g(α)

Proof:

(1) Assume that g(α) is a cyclotomic integer made up of periods of length f.

(2) Then, there exists a_i and η_i such that:

g(α) = a₀ + a₁η₀ + a₂η₁ + ... + a_eη_e-1

(3) Applying σ^e to g(α) gives us:

σ^eg(α) = a₀ + a₁σ^eη₀ + ... + a_eσ^eη_e-1

(4) Applying Lemma 2 above gives us:

σ^eg(α) = a₀ + a₁η₀ + ... + a_eη_e-1

(5) Assume that σ^eg(α) = g(α)

(6) Then by Corollary 1.2 above, g(α) consists of e periods.

(7) And by Lemma 3, each period will be of length f.

QED

Corollary 4.1: The product of two cyclotomic integers made up of periods of length f is itself made up of periods of length f.

Proof:

(1) Let f(α), g(α) be cyclotomic integers made up of periods of length f so that:

σ^ef(α) = f(α)
σ^eg(α) = g(α)

(2) But then:

σ^e[f(α)g(α)] = [σ^ef(α)][σ^eg(α)] = f(α)g(α)

(3) So that by Lemma 4 above, we have proved that f(α)g(α) must itself be made up of periods of length f.

QED

Example: λ = 13, f = 3, e = 4

We note that:

(η₀)² = η₁ + 2η₂

η₀η₁ = η₀ + η₁ + η₃

η₀η₂ = 3 + η₁ + η₃

Likewise, applying σ to these equations gives us:

(η₁)² = η₂ + 2η₀

η₁η₂ = η₁ + η₂ + η₀

And so forth.