## Primitive roots of unity

Let us recall that an element is a zero divisor if and there exists such that and .

Let us recall also that because the ring has a unit then there is a map

 (1)

which allows to talk of an integer as an element of . However a nonzero integer may become . For instance every multiple of becomes 0 in .

Observe also the ring may contain nonzero elements that are neither zero divisor, nor units. For instance in the ring of square matrices of order 2 with integer coefficients the matrix is nonsingular but has no inverse (right or left). But this is not a good example since we limit ourselves to commutative rings. So consider instead the following example.

Example 1   Let and let be the ring of univariate polynomials over . The ring has units (for instance the constant polynomial ), it has zero divisors (for instance the polynomial since ) and also elements like which is not a unit nor a zero divisor.

Why do we need to take such exotic examples? Because among the rings you are familiar with, this is the simplest example of ring having zero divisors, units and nonzero elements that are not zero divisors or units. Indeed our usual rings are where is a field and the residue class ring (with not necessarily prime). The ring has no zero divisors whereas has zero divisors iff is not prime. But for every non prime the ring consists only of zero, units and zero divisors. This follows from the proposition below. This is why we were led to the example.

Proposition 1   Let be an Euclidean domain and an element of with and . Consider the residue class ring where denotes the ideal generated by . Then every element of is either zero, a zero divisor or a unit.

Proof. Studying the elements of (for deciding if they are null, zero divisors or units) can be done by studying the for every . So let be in . If is a multiple of then . Assume from now on that is not a a multiple of . Consider the gcd of and together with the Bezout relation

 (2)

Observe that cannot be zero (otherwise would be zero and would divide and thus ). If then and this shows is a unit of . The same result holds if is a unit. Assume from now on that is not a unit. Since divides and let and be such that

 (3)

Observe that is not zero (otheriwse would write leading to the contradiction ). We have

 (4)

This shows that is a zero divisor of . Yes, this was that simple!

Definition 1   Let be a positive integer and .
1. is a -th root of unity if .
2. is a primitive -th root of unity if
1. ,
2. is a unit in ,
3. for every prime divisor of the element is neither zero nor a zero divisor.

Remark 1   When is an integral domain the last condition of Definition 1 becomes: for every prime divisor of the element . Observe also that a -th root of unity is necessarily a unit.

Example 2   Consider that is the field of complex numbers. The number is a a primitive -th root of unity.

Example 3   In we have . However is not a primitive -th of unity, since is not a unit in .

Example 4   In we have the following computation in AXIOM
(1) -> R := PF(17)

(1)  PrimeField 17
Type: Domain
(2) -> w: R := 3

(2)  3
Type: PrimeField 17
(3) -> [w^i for i in 0..16]

(3)  [1,3,9,10,13,5,15,11,16,14,8,7,4,12,2,6,1]
Type: List PrimeField 17
(4) -> u: R := 2

(4)  2
Type: PrimeField 17
(5) -> [u^i for i in 0..16]

(5)  [1,2,4,8,16,15,13,9,1,2,4,8,16,15,13,9,1]
Type: List PrimeField 17

The first list shows that is a primitive -th root of unity. However with we have since .

Lemma 1   Let be integers and let be a primitive -th root of unity. Then we have
1. is neither zero nor a zero divisor in ,
2. .

Proof. It relies on the formula

 (5)

which holds for every and every positive integer .

Let us prove the first statement of the lemma. Let be the gcd of and . Let be such that

 (6)

Since we have . Hence we can cancel a prime factor of such that

 (7)

Let

 (8)

 (9)

for some . Hence if would be zero or a zero divisor then so would be which is false. Now applying Relation (5) with and implies that divides . But with Relation (6) we obtain

 (10)

Hence

 (11)

Therefore cannot be zero or a zero divisor.

Now let us prove the second statement of the lemma. By applying Relation (5) with and we have

 (12)

Since is neither zero nor a zero divisor we otain the desired formula.

Marc Moreno Maza
2008-01-07