Roots of Unity: The Cyclotomic Polynomial

Since 1 is always a root of unity, we can determine the other roots of unity by dividing (xⁿ - 1) by (x -1) and solving the equation.

In the case of n=2, this gives us: (x² - 1)/(x - 1) = (x + 1). So, the other root of unity is x = -1.

In the case of n=3, this gives us: (x³ - 1)/(x - 1) = (x² + x + 1). Using the quadratic equation to solve for this (see Theorem, here) gives us:

(-1 ± √1 - 4)/2 = (-1 ± √-3)/2.

In light of this and a previous result (see Lemma 1, here), it is possible to generate an equation to determine the primitive nth roots of unity.

Definition 1: Cyclotomic Polynomial Φ_n(x)

Φ₁(x) = x - 1

Otherwise:



where d includes all divisors of n except for n itself.

Lemma 1:

If p is prime, then:

Φ_p = x^p-1 + x^p-2 + ... + x + 1

Proof:

(1) Since p is prime, the only divisor is 1 and:

Φ_p = (x^p - 1)/(x - 1)

(2) Now, we know that (x^p - 1)/(x - 1) = x^p-1 + x^p-2 + ... + x + 1 since:

(a) Let s = x^p-1 + x^p-2 + ... + x + 1

(b) x*s = x^p + x^p-1 + ... + x² + x

(c) x*s - s = x^p - 1

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

(e) s = (x^p - 1)/(x - 1)

QED

Now, the next thing we need is a proof that Φ_n will generate a polynomial whose solution is the primitive n-th roots of unity:

Theorem 2: Cyclotomic Polynomial

For every integer n ≥ 1, Φ_n is a monic polynomial (see Definition 5, here for monic if needed) with integral coefficients and:

Φ_n = ∏(x - ζ) ∈ Z[x]

where ζ runs over the set of primitive n-th roots of unity and Z is the set of integers.

Proof:

(1) For Φ₁=x-1, the theorem is clearly true.

(2) Let's assume that the theorem is true up to n-1.

(3) Since d is always less than n, for each d, we have:

Φ_d(x) = ∏(x - ζ) ∈ Z[x]

where ζ runs over the roots of unity with exponent d.

(4) Since each root of Φ_d is a root of unity, it follows that Φ_d divides xⁿ - 1 [see Lemma 1, here]

(5) If d₁, d₂ are distinct divisors of n, then it follows that Φ_d1 and Φ_d2 are relatively prime polynomials and distinct -- that is, they do not include any common root of unity since:

Each root of unity has a unique exponent so no root of unity included in Φ_n will be found in more than one divisor Φ_di.

(6) Using Corollary 2.2, here, it follows that:



is a polynomial since it is divible by a product of all Φ_d

(7) Since each Φ_d is monic, it follows that Φ_n is monic.

(8) Since each Φ_d is in Z[x] and since xⁿ - 1 is in Z[x], using the Division Algorithm for Polynomials, it follows that Φ_n is in Z[x]. [See Theorem, here]

(9) Now for each (x - ζ_i) that divides Φ_n, it follows that it's exponent equals n since:

(a) If its exponent is less than n and it is an n-th root of unity, then its exponent e is a divisor of n and it has been divided out.

(b) Assume that e doesn't divide n.

(c) So that n = qe + r where r ≥ 1 and r is less than e.

(d) Then:

(ζ)^qe+r = 1 = (ζ)^qe*(ζ^r)

(e) We know that (ζ)^qe = 1 since:

(ζ)^qe = (ζ^e)^q

(f) But then:

ζ^r = 1/(ζ^qe) = 1

(g) This is impossible since r is less than e and e is the exponent of the root of unity.

(h) Therefore, we reject the assumption in 9b.

QED

References

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

Primitive Roots of Unity

In analyzing whether a root of unity is expressible as a radical, it is valuable to leverage the idea of a primitive root of unity. This root of unity has the following properties:

(1) The primitive n-th root of unity only equals 1 when it is raised to a power that is a multiple of n.
(2) If ζ is a primitive n-th root of unity, then the n distinct n-th roots of unity are: ζ⁰, ζ¹, ..., ζ^n-1

Definition 1: Exponent e of an n-th root of unity

The exponent e of an n-th root of unity ζ is the smallest integer such that e is greater than 0 and ζ^e = 1.

Examples:

The exponent of 1 is 1.

The exponent of -1 is 2.

Definition 2: Primitive n-th roots of unity

An n-th root of unity is primitive if and only if its exponent is n.

Example:

-1 is a primitive square (second) root of unity since (-1)² = 1.

1 is not a primitive square (second) root of unity since (1)¹ = 1.

i, -i are primitive fourth roots of unity.

1, -1 are not primitive fourth roots of unity.

Lemma 1:

For a root of unity ζ, ζ^m = 1 if and only if its exponent e divides m.

Proof:

(1) Assume that e divides m.

(2) Then there exists f such that m = ef.

(3) So ζ^m = ζ^ef = (ζ^e)^f = (1)^f = 1

(4) Assume that ζ^m = 1

(5) Let d = gcd(e,m)

(6) By Bezout's Identity (see Lemma 1, here), there exists r,s such that:

mr + es = d

(7) Now,

ζ^d = ζ^mr*ζ^es = (ζ^m)^r*(ζ^e)^s = (1)^r*(1)^s = 1

(8) But since e is the smallest number whereby (ζ)^e = 1, it follows that e ≤ d.

(9) But since d divides e, it follows that d ≤ e.

(10) It therefore follows (see Lemma 2, here) that d = e.

(11) Since d divides m, it follows that e divides m.

QED

Theorem 2:

Let ζ, η be roots of unity of exponents e and f.

If e and f are relatively prime, then ζ*η is a root of unity of exponent e*f.

Proof:

(1) By definition 1 above:

ζ^e = 1

η^f = 1

so that:

(ζ*η)^ef = (ζ)^ef*(η)^ef = (ζ^e)^f*(η^f)^e=(1)^f*(1)^e=1

(2) This shows that ζ*η is a root of unity.

(3) Let k be the exponent of (ζ*η).

(4) From Lemma 1 above, we know that k divides e*f.

(5) Since:

(ζ*η)^k = 1

It follows that:

(ζ*η)^k = ζ^k*η^k = 1

So that:

ζ^k = η^-k

(6) Raising both sides to the power of f gives us:

(ζ^k)^f = ζ^kf = (η^-k)^f = η^(-kf) = (η^f)^-k = (1)^-k = 1

(7) So by Lemma 1 again, we see that e divides kf.

(8) But gcd(e,f)=-1 so e must divide k. [see Lemma 3, here]

(9) We can make the same argument in step #5 (by switching ζ and η) to show that f must also divide k.

(10) Since gcd(e,f)=1 and e divides k and f divides k, it follows (see Lemma 1, here) that ef divides k.

(11) Since ef divides k and k divides ef, it follows (see Lemma 2, here) that k=ef.

QED

Theorem 3: Powers of a Primitive N-th Root of Unity

Let ζ be a primitive n-th root of unity

Then:

every n-th root of unity is a power of ζ

Proof:

(1) Since ζ is an n-th root of unity, all powers of ζ are n-th roots of unity:

(ζⁱ)ⁿ = (ζ)ⁱⁿ = (ζⁿ)ⁱ = (1)ⁱ = 1

(2) Next, we will show that each of these n powers (ζ⁰, ζ¹, ..., ζ^n-1) are distinct.

(3) Assume that they are not distinct.

(4) Then, there exists a distinct i,j such that:

0 ≤ i,j ≤ n-1

and

i ≠ j

and

ζⁱ = ζ^j

(5) Assume that j is greater than i.

(6) From step #4, we have:

1 = ζ^j/ζⁱ = ζ^j-i

(7) But since j,i are less than n, it follows that j-i is greater than 0 and less than n.

(8) But this is impossible since by definition, we know that n is the exponent of ζ

(9) So, we reject our assumption in step #5

(10) We know that there are exactly n roots of unity by applying the Fundamental Theorem of Algebra which says that xⁿ - 1 = 0 has exactly n roots. [See Theorem, here]

QED

References

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

Roots of Unity: Expressed as Radicals

In a previous blog, I showed how the roots of unity can be stated as trigonometric functions. The question remains about when and under what conditions, they can be expressed as radicals. After all, this is clearly the case if n is a power of 2.

Abraham de Moivre made significant progress in investigating this question. In today's blog, I will show that we can answer the case of a composite number. If n is a nonprime such that n=rs and the r-th roots of unity can be expressed as radicals and the s-th roots of unity can be expressed as radicals, then it follows that the n-th root of unity can be expressed as radicals.

Lemma 1:

Let r,s be positive integers
Let μ₁, μ₂, ..., μ_r be the r-th roots of unity.
Let ζ₁, ζ₂, ..., ζ_s be the s-th roots of unity.

Then:

The rs-th roots of unity are of the form:



for i = 1, ..., r and j = 1, ..., s.

Proof:

(1) Using an earlier result (see Lemma 1, here), we have:



(2) Setting Y = X^r gives us:



(3) Using de Moivre's equation (see Theorem 1, here), we know that:



(4) Combining step #2 and step #3, we have:



QED

Theorem 2:

Let n be a positive integer.

If for each prime p factor of n, the p-th root of unity is expressible as radicals, then the n-th root of unity is expressible as radicals

Proof

(1) If n is a prime number, then the theorem is true by definition. So, for n=2, this theorem holds.

(2) Assume that there exists some number n such that the theorem holds true for all numbers less than n.

(3) If n is a prime, then the theorem is true and we are done. So, we assume that n is not a prime.

(4) Then there exists two numbers r,s such that r≠ 1 and s≠1 and n =rs.

(5) Since by assumption the r-th roots of unity and the s-th roots of unity are expressible by radicals, we can apply Lemma 1 above to conclude that n-th roots of unity must also be expressible by radicals.

QED

The implication of Theorem 2 is that to determine which n-th roots of unity are expressible as radicals, we only need to consider the cases where n is a prime number.

References

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

Proof for Cotes' Formulas

In today's blog, I will show how De Moivre's Formula can be used to establish Cotes' Formulas.

Lemma 1:

Let μ_n be the set of all nth roots of unity

Then:



Proof:

(1) We know that xⁿ - 1 has n root from the Fundamental Theorem of Algebra.

(2) We also note that for all ζ, we have (ζ)ⁿ = 1

(3) Based on #2, the Fundamental Theorem of Algebra gives us:

xⁿ - 1 = (x - ζ₁)*(x - ζ₂)*(x - ζ₃)*...*(x - ζ_n)

(4) Step #3 can then be restated as:



QED

Corollary 1.1:



Proof:

This follows from applying De Moivre's proof [see Corollary 1.1, here] for the existence of the roots of complex numbers with the result in Lemma 1 above.

QED

Corollary 1.2:



Proof:

This follows from applying De Moivre's proof [see Corollary 1.2, here] for the existence of the roots of complex numbers with the result in Lemma 1 above.

QED

Theorem 2:

If n is odd:


If n is even:

Proof:

(1) From Corollary 1.1 above, we have:



(2) Now, we can remove the k=0 case to get the following:



(3) Now, it is also possible to pair up roots. That is, let l = n - k.

(4) Then we have:

cos(2[(n-k)π]/n) =
=cos([2nπ - 2kπ]/n) =
=cos([2nπ/n] - [2kπ/n]) =
=cos(2π - 2kπ/n) =
cos(-2kπ/n) = cos(2kπ/n) [See Property 9, here]

sin(2[(n-k)π]/n) =
=sin([2nπ - 2kπ]/n) =
=sin([2nπ/n] - [2kπ/n]) =
=sin(2π - 2kπ/n) =
=sin(-2kπ/n) = -sin(2kπ/n) [See Property 4, here]

(5) So, pairing the roots of unity k with its n-k pair gives us:















(6) So, if n is odd, we have:



(7) If n is even, then at k=n/2 we have:

cos([2(n/2)π]/n) = cos(nπ/n) = cos(π) = -1 [See Property 6, here]

sin([2(n/2)π]/n) = sin(nπ/n) = sin(π) = 0 [See Property 1, here]

So:

[x - cos([2(n/2)π];/n) - isin([2(n/2)π]/n)] =

= x - (-1) - i*0 = x + 1

(8) So, if n is even, we have:



since we can see that n/2 is not included in any of the pairings:

k = 1 .. (n/2)-1

n-k = (n/2)+1 .. n-1

QED

Corollary 2.1:




Proof:

(1) Assume that n is odd.

(2) Then from Theorem 2 above, we have:



(3) Since n is odd, there exists m such that n = 2m+1.

(4) This then gives us:



(5) Setting x = (a/x) gives us:



(6) Multiplying both sides by x^2m+1 gives us:


(7) Assume that n is even.

(8) Then, from Theorem 2 above we have:



(9) Since n is even, there exists an integer m such that n = 2m.

(10) This then gives us:



(11) Setting x = (a/x) gives us:



(12) Multiplying both sides by x^2m gives us:


QED

Theorem 3:

If n is odd:



If n is even:



Proof:

(1) From Corollary 1.2 above, we have:



(2) Now, it is also possible to pair up roots. That is, let l = n - k -1.

(3) Then we have:

cos([2(n-k-1)+1]π/n) =
=cos([2n - 2k -1]π/n) =
=cos([2nπ/n] - [(2k+1)π/n] ) =
=cos(2π - (2k+1)π/n) =
cos(-[2k+1]π/n) = cos([2k+1]π/n) [See Property 9, here]

sin([2(n-k-1)+1]π/n) =
=sin([2n - 2k - 1]π/n) =
=sin([2nπ/n] - [(2k+1)π/n]) =
=sin(2π - (2k+1)π/n) =
=sin(-[2k+1]π/n) = -sin([2k+1]π/n) [See Property 4, here]

(4) So, pairing each roots of unity k with its n-k-1 pair gives us:















(5) If n is even, the we have:



(6) If n is odd, then at k=(n-1)/2:





and







(7) So:



= x - (-1) - i*0 = x + 1


(8) So, if n is odd, we have:



since we can see that (n-1)/2 is not included in any of the pairings:

k = 0 .. (n-1)/2 - 1

n-k-1 = (n-1)/2 + 1 .. n-1

since:

n-[(n-1)/2 - 1] - 1 =
= n - (n-1)/2 + 1 - 1 =
= (2n - [n-1])/2 =
= (n + 1)/2 =
= (n - 1 + 2)/2 =
(n-1)/2 + 1

QED

Corollary 3.1:




Proof:

(1) Assume that n is odd.

(2) Then from Theorem 3 above, we have:



(3) Since n is odd, there exists m such that n = 2m+1.

(4) This then gives us:



(5) Setting x = (a/x) gives us:



(6) Multiplying both sides by x^2m+1 gives us:



(7) Assume that n is even.

(8) Then, from Theorem 3 above we have:



(9) Since n is even, there exists an integer m such that n = 2m.

(10) This then gives us:



(11) Setting x = (a/x) gives us:



(12) Multiplying both sides by x^2m gives us:



QED

References

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001