Saturday, January 05, 2008

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: ζ0, ζ1, ..., ζ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)2 = 1.

1 is not a primitive square (second) root of unity since (1)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 = ζmres = (ζ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 = ζkk = 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:

i)n = (ζ)in = (ζn)i = (1)i = 1

(2) Next, we will show that each of these n powers 0, ζ1, ..., ζ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

ζi = ζj

(5) Assume that j is greater than i.

(6) From step #4, we have:

1 = ζji = ζ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 xn - 1 = 0 has exactly n roots. [See Theorem, here]

QED

References




1 comment:

chera said...

Nicely explained. My request is Without using complex numbers kindly show the existence of primitive roots.