Cyclotomic Integers: More x + αiy

In today's blog, I continue going through lemmas from Harold Edward's Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory. I am continuing down the same section that I started in my previous blog. If you would like to start at the beginning of cyclotomic integer properties, start here.

I will use many of these properties later when I go over Kummer's proof of Fermat's Last Theorem for regular primes.

Lemma 1:

if f(α) ≡ g(α) (mod h(α)) → f(k) ≡ g(k) (mod p) with α^λ = 1 and λ is a prime.

then k^λ ≡ 1 (mod p)

Proof:

(1) Let f(α) = α^λ-1 + α^λ-2 + ... + α + 1.

(2) We know that f(α) = 0 [See Lemma 2 here for proof if needed]

(3) So we have f(α) ≡ 0 (mod h(α)) [See here if you need a review of modular arithmetic]

(4) But from assumption f(α) ≡ g(α) (mod h(α) → f(k) ≡ g(k) (mod p) so:

f(k) ≡ 0 (mod p)

(5) So k^λ-1 + k^λ-2 + ... + k + 1 ≡ 0 (mod p)

(6) Now, if we multiply (k-1) to this result:

(k-1)(k^λ-1 + k^λ-2 + ... + k + 1) =

= k^λ + k^λ-1 + ... + k² + k - k^λ-1 - k^λ-2 - ... - k - 1 =

= k^λ - 1

(7) Now combining step #5 and step #6 gives us:

k^λ - 1 ≡ 0 (mod p)

Which is the same as:

k^λ ≡ 1 (mod p)

QED

Lemma 2:

If k is an integer and p is a prime such that k^j ≡ 1 (mod p)

Then, there exists a smallest nonzero integer d such that k^j ≡ 1 (mod p) if and only if d divides j.

Proof:

(1) By the Well-Ordering Principle, we know that there must be a smallest nonzero integer where k^d ≡ 1 (mod p)

(2) Let us assume that k^j ≡ 1 (mod p) but d doesn't divide j.

(3) Using the Division Algorithm, we know that there exists q,r such that:

j = dq + r and 1 ≤ r ≤ d-1

(4) Then k^j ≡ 1 (mod p) implies that:

k^dq+r ≡ 1 (mod p)

and further, we note that:

k^{dq + r} ≡ (k^dq)*(k^r) ≡ [(k^d)^q]*(k^r) ≡ (1)(k^r) ≡ k^r ≡ 1 (mod p)

(5) But this is impossible since d is the lowest nonzero value such that k^d ≡ 1 (mod p) so we reject our assumption in #2.

(6) Now, let's assume that d divides j.

(7) So, then there exists a value q such that:

k^j ≡ k^dq ≡ (k^d)^q ≡ (1)^q ≡ 1 (mod p).

QED

Lemma 3:

If h(α) is a prime cyclotomic integer which divides a binomial x + α^jy (where x,y are relatively prime integers and α^j ≠ 1) and α^λ = 1 where λ is a prime.

Then there exists a prime p such that h(α) divides p and either p = λ or p ≡ 1 (mod λ)

Proof:

(1) Let h(α) be a prime cyclotomic integer which divides a binomial x + α^jy

(2) We know that there exists a prime p such that h(α) divides p. [See Lemma 1 here for proof]

(3) We know from Lemma 1 above that there exists an integer k such that:

k^λ ≡ 1 (mod p)

(4) We also know from Lemma 2 above that there exists a minimum element d such that α^d ≡ 1 (mod p) and since α^λ ≡ 1 (mod p), we know that d = 1 or d = λ

(5) Assume d = 1.

We will show that this implies that λ = p

(6) Then k¹ ≡ 1 (mod p)

(7) From Lemma 1 above, we know that:

k^λ-1 + k^λ-2 + ... + k + 1 ≡ 0 (mod p)

So applying step #6 gives us:

(1)^λ-1 + (1)^λ-2 + ... + (1)¹ + 1 ≡ λ ≡ 0 (mod p)

(8) This implies that p divides λ but since both p, λ are primes, this is only possible if λ = p.

(9) Assume d= λ.

We will show that this implies that p ≡ 1 (mod λ)

(10) Using Fermat's Little Theorem, we know that:

k^p-1 ≡ 1 (mod p)

(11) From Lemma 2 above, this tells us that λ must divide p-1.

(12) So that we conclude that p ≡ 1 (mod λ)

QED

Lemma 4: if n is an odd prime, then

(x - α)(x - α²)*...*(x - α^n-1) = x^n-1 + x^n-2 + ... + 1

Proof:

(1) From a previous result, we have:

xⁿ - 1 = (x - 1)(x - α)(x - α²)*...*(x - α^n-1)

(2) Now xⁿ - 1 divided by x-1 = x^n-1 + x^n-2 + ... + x + 1 since:

(x-1)(x^n-1 + x^n-2 + ... + x + 1) =

= xⁿ + x^n-1 + x^n-2 + .... + x² + x -x^n-1 - x^n-2 - .... - x² - x - 1 =

= xⁿ - 1

(3) Putting #2 and #1 together gives us:

x^n-1 + x^n-2 + ... + x + 1 = (x - α)(x - α²) * ... * (x - α^n-1)

QED

Lemma 5:

if h(α^j) divides h(αⁱ) where i is not congruent to j modulo λ then

Nh(α) divides N(α^j-i-1)

Proof:

(1) Let k be an integer such that k ≡ α (mod hα) [For proof that this value exists, see Lemma 3 here]

(2) Since conjugates preserve relations (see Lemma 2.5 here), we also know that:

α^j ≡ k (mod h(α^j))

αⁱ ≡ k (mod h(αⁱ))

(3) Since h(α^j) divides h(αⁱ), we also have:

αⁱ ≡ k (mod h(α^j))

(4) Combining #2 and #3 gives us:

α^j ≡ k ≡ αⁱ (mod h(α^j))

(5) So h(α^j) divides α^j - αⁱ

(6) So Nh(α^j) divides N(α^j - αⁱ) [See Lemma 6 here]

(7) But since Nh(α) = Nh(α^j) (see Lemma 3 here), this gives us that:

Nh(α) divides N(α^j - αⁱ)

(8) Now, since α^j - αⁱ = αⁱ(α^j-i - 1), it follows that (see Lemma 6 here):

N(α^j - αⁱ) = N(αⁱ)*N(α^j-i-1)

(9) Finally, N(αⁱ) = 1 since:

(a) N(αⁱ) = N(α) = α*α²*...*α^λ-1 = α^{1+2+3+...+λ-1}

(b) 1 + 2 + 3 + ... + λ - 1 = (1/2)(λ - 1)λ since:

(1 + λ - 1) + (2 + λ - 2) + ... + (λ - 1 + 1) = 2 * (1 + 2 + 3 + ... + λ - 1)

Further, this result is = to (1 + λ -1) = λ so that we have (λ - 1)*(λ) = 2*(1 + 2 + 3 + ... + λ -1)

So dividing both sides by 2 gives us:

(1/2)(λ - 1)*(λ) = 1 + 2 + 3 +... + λ - 1)

(c) Since λ is odd, we know that λ - 1 is even so there exists a rational integer x such that x = (1/2)(λ - 1)

(d) So we get: 1 + 2 + 3 + ... + λ - 1 = x(λ)

(e) So putting it all together:

N(α) = α^{1 + 2 + 3 + ... + λ-1} = α^x(λ)) = (α^λ)^x = 1.

(10) So, Nh(α) divides N(α^j-i - 1)

QED

Lemma 6:

If h(α) is a prime cyclotomic integer which divides a binomial x + α^jy (where x,y are relatively prime integers and α^j ≠ 1),

then Nh(α) is a prime integer which is congruent to 0 or 1 modulo λ

Proof:

(1) Let h(α) be a prime cyclotomic integer that divides x + α^jy.

(2) Then, there exists a prime integer p such that h(α) divides p. [See Lemma 1 here for proof]

(3) Using Lemma 3 above we know that p ≡ 0 (mod λ) or p ≡ 1 (mod λ).

(4) From a previous result (Lemma 3 here), we know that there exists an integer k such that:

k ≡ α (mod h(α))

(5) Assume p = λ (see Lemma 3 above since this is the case where p ≡ 0 (mod λ))

We will now show that N(h(α)) = p.

(6) There exists an integer d such that d is the minimum positive integer where k^d ≡ 1 (mod p) [See Lemma 2 above]

(7) Then d = 1 since (from Lemma 3 above) if d ≠ 1, then d = λ which implies that p ≡ 1 (mod λ) which contradicts assumption in #4 so we conclude d=1.

(8) So k ≡ 1 (mod p) since k^d ≡ 1 (mod p) [See Lemma 3 above for details if needed]

(9) So, combining step #8 with step #4 gives us:

α ≡ 1 (mod p)

and since h(α) divides p, this also gives us:

α ≡ 1 (mod h(α))

(10) This shows that h(α) divides α - 1.

(11) This also shows that Nh(α) divides N(α - 1) [See Lemma 6 here for details if needed]

(12) N(α - 1) = N(1 - α) since:

N(α - 1) = (α - 1)(α² - 1)*...*(α^n-1 - 1)

N(1 - α) = (-1)^n-1[(α - 1)(α² - 1)*..*(α^n-1 - 1)

Since n is odd, n-1 is even and (-1)^n-1 = 1

(13) N(1 - α) = (1 - α)(1 - α²)*...*(1 - α^n-1) [See here for definition of norm for cyclotomic integers]

(14) From Lemma 4 above:

(x - α)(x - α²)*...*(x - α^n-1) = x^n-1 + x^n-2 + ... + x + 1

(15) Setting x = 1 gives us:

(1 - α)(1 - α²)*...*(1 - α^n-1) = 1^n-1 + 1^n-2 + ... + 1 + 1 = n

(16) Since in this case n= λ, this proves that N(α - 1) = λ

(17) Now h(α) divides (α - 1) (step #10), this also gives us that Nh(α) divides N(α - 1) which means that Nh(α) divides p.

(18) But p is a prime and since Nh(α) ≠ 1 (since h(α) is a cyclotomic prime, see here for more details), we are left with concluding that Nh(α) = p.

(19) Assume p ≡ 1 (mod λ).

We will now show that under this condition, Nh(α) = p

(20) Since k ≡ α (mod h(α)) [from step #4] we know that:

(a) h(α) divides k - α

(b) And therefore h(α^j) divides k - α^j since conjugates preserve relations (see Lemma 2.5 here)

(21) Now we know that no conjugate of h(αⁱ) divides another conjugate of h(α^j) where i is not congruent to j modulo λ since:

(a) Assume h(α^j) divides h(αⁱ) and i is not congruent to j (mod h(α))

(b) Then Nh(α) divides N(α^j-i-1) [See Lemma 5 above]

(c) But since i is not congruent to j (mod h(α)), N(α^j-i-1) = N(α - 1) [See Lemma 5 above]

(d) So that using the reasoning from #12 thru #16 gives us that:

N(α^j-i-1) = λ

(e) But then h(α) divides λ which is impossible since p does not divide λ from step #19 so we have a contradiction and we reject our assumption in step #21a.

(22) Since h(α) divides p, there exists a cyclotomic integer q(α) such that:

p = h(α)*q(α)

(23) Now we know that each of the other conjugates of h(α) must also divide p since h(α) divides p implies Nh(α) divides N(p) so that h(α)*h(α²)*...h(α^n-1) divides p*p*...*p.

(24) Since h(α²) divides p, it divides h(α)*q(α) but it cannot divide h(α) from step #21 so it divides q(α) [See here for reason that Euclid's Lemma applies to cyclotomic integers]

(25) We can therefore conclude that there exists q₂(α) such that q(α) = h(α²)*q₂(α)

(26) We can repeat step #24 and step #25 for each conjugate of h(α) until we get:

p = h(α)*h(α²)*...h(α^n-1)*q_n-1(α)

So that we get:

p = Nh(α)*q_n-1(α)

(27) But since p is a prime integer and Nh(α) is a rational integer, q_n-1(α) must also be a rational integer.

(28) But p is prime so the only values that can divide it are p and 1. Since we know that Nh(α) ≠ 1, this means that Nh(α) = p and q_n-1(α) = 1.

QED

Corollary 6.1: If Nh(α) = λ, then h(α) and all of its conjugates are unit multiples of α - 1.

Proof:

(1) Let Nh(α) = λ

(2) From Lemma 6 above, we know that there exists an integer k such that k ≡ 1 (mod p)

(3) Since k ≡ α (mod p) (from Lemma 6 above), this also means that α ≡ 1 (mod p).

(4) This shows that p divides α - 1 which means likewise that h(α) divides α - 1 since h(α) divides p.

(5) Then, there exists a value q(α) such that α - 1 = h(α)q(α)

(6) Using Lemma 6 here, we get:

N(α - 1) = Nh(α)*Nq(α)

(7) From step #16 in Lemma 6 above, we know that N(α - 1) = λ

(8) But we also know from Lemma 6 above that Nh(α) = p = λ

(9) So we see that Nq(α) = 1 which means that q(α) is a cyclotomic unit (see here for definition of a cyclotomic unit)

(10) Since all the conjugates of h(α) divide p (see Lemma 6 above for details), we can make the same argument for each of them.

QED

Lemma 7:

If h(α) is any cyclotomic integer whose norm is a prime integer, then h(α) is prime and it divides a binomial x + α^jy (x,y relatively prime, α^j ≠ 1)

Proof:

(1) Let h(α) be a cyclotomic integer whose norm Nh(α) is a prime integer p

(2) Let k be an integer such that k^λ ≡ 1 (mod p) where λ is an odd prime.

(3) Let γ be a primitive root mod p. (See here for details on primitive roots if needed)

(4) Then every nonzero integer mod p can be written in a form of γⁱ where i = 1, 2, ..., p - 1). [See here for definition of primitive root]

(5) We also see that by Fermat's Little Theorem, (γⁱ)^λ ≡ 1 (mod p) if and only if p-1 divides iλ

(6) In Lemma 6 above, this theorem has been proven for the case p = λ so we can assume that p ≡ 1 (mod λ)

(7) Based on this assumption, there exists a value μ such that p - 1 = λμ

(8) From step #5, we know that p-1 divides iλ if and only if μ divides i since:

(a) From step #7, μ = (p-1)/λ

(b) Assume p - 1 divides iλ

(c) p-1 = λ*μ

(d) So λ*μ divides i λ

(e) Since λ cancels out, this means that μ must divide i.

(f) Assume μ divides i

(g) Then λ*μ divides i*λ

(h) Which means that p-1 divides i*λ

(9) Let m = γ^μ

(10) If k = m, m², m³, ..., then:

k^λ ≡ 1 (mod p) [This follows from step #8, step #9]

(11) h(m)*h(m²)*...*h(m^λ-1) ≡ 0 (mod p) since:

(a) Using the Division Algorithm for polynomials (see here), we know that there exists q(x), r(x) such that:

h(x)*h(x²)*...*h(x^λ-1) = q(x)(x^λ-1 + x^λ-2 + ... + 1) + r(x)

where the degree of r(x) is a polynomial of degree less than λ - 1.

(b) Since Nh(α) = p and since α^λ-1 + α^{λ - 2} + ... + 1 = 0 (see Lemma 2 here), we get:

p = q(α)(0) + r(α)

so that r(x) = p

(c) Using step #11b, we get:

h(m)*h(m²)*...*h(m^λ-1) = q(m)(m^λ-1 + m^{λ - 2} + ... + 1) + p.

(d) Now, from an earlier result (see step #6 in Lemma 1 above), we know that:

(m^λ - 1)/(m - 1) = m^λ-1 + m^{λ - 2} + ... + 1

(e) We also know that m is not congruent 1 (mod p) since:

μ divides p-1 from step #7 above

So μ is less than p-1.

The order of γ is p-1 [See here for definition of order of a primitive root]

So therefore m = γ^μ cannot be congruent to 1 (mod p)

(f) Since m^λ ≡ 1 (mod p) from step #10 and since m is not congruent 1 (mod p) , we get:

(m^λ - 1)/(m - 1) ≡ (1 - 1)/(m - 1) ≡ 0 (mod p)

(12) From this, we know that at least one of the values h(m^j) ≡ 0 (mod p)

(13) Using the Division Algorithm for Polynomials with h(x), we have:

h(x) = q(x)(x - m^j) + r where 1 ≤ j ≤ λ -1.

We see that r is an integer.

(13)Using h(m^j) = q(m^j)(m^j - m^j) + r shows that r = h(m^j) and from step #12, we can assume that r ≡ 0 (mod p)

(14) So h(αⁱ) ≡ q(αⁱ)(αⁱ - m^j) (mod p) for i = 1, 2, ..., λ - 1.

(15) Now, from step #14, we get:

(α - m^j)*h(α²)*h(α³)*...*h(α^λ-1) ≡

≡ (α - m^j)q(α²)(α² - m^j)q(α³)*(α³ - m^j)* ... * q(α^λ-1)(α^λ-1 - m^j) ≡

≡ N(α - m^j)q(α²)q(α³)*...*q(α^λ-1) (mod p)

(16) Now, since (x - α)*...*(x - α^λ-1) = (x^λ - 1)/(x - 1) [See here], we know that:

N(α - k) = (k^{λ - 1})/(k - 1) ≡ (1 - 1)/(k - 1) ≡ 0 (mod p)

(17) And since k can equal m^j (see step #10), we have shown that N(α - m^j) ≡ 0 (mod p).

(18) This proves that h(α) divides α - m^j since h(α) divides p.

(19) Now, we need only to prove that h(α) is prime to complete the proof.

(20) Assume that h(α) divides f(α)g(α)

(21) Then f(α)g(α) ≡ 0 (mod h(α))

(22) Since α ≡ k (mod h(α)), we also have:

f(k)g(k) ≡ 0 (mod h(α))

(23) We also have f(k)g(k) ≡ 0 (mod p) since:

(a) Assume f(k)g(k) ≡ w (mod p) and w is not congruent to 0.

(b) Then f(k)g(k) ≡ w (mod h(α)) since h(α) divides p.

(c) And then w ≡ 0 (mod h(α)) which is impossible so we reject our assumption at (#23a)

(24) Now p either divides f(k) or g(k) by Euclid's Lemma.

(25) So finally, h(α) must divide either f(k) or g(k).

(26) And since k ≡ α (mod h(α)), we also have:

h(α) must divide either f(α) or g(α).

QED