Primitive roots of unity

Let us recall that an element a $\in$ R mathend000# is a zero divisor if a $\neq$ 0 mathend000# and there exists b $\in$ R mathend000# such that a b = 0 mathend000# and b $\neq$ 0 mathend000#.

Let us recall also that because the ring R mathend000# has a unit 1 mathend000# then there is a map

$$\mbox{${\mathbb Z}$}$$	$$\longmapsto$$	R
n	$$\longmapsto$$	n 1R

(1)

which allows to talk of an integer as an element of R mathend000#. However a nonzero integer n mathend000# may become 0_R mathend000#. For instance every multiple of p mathend000# becomes 0 mathend000# in $\mbox{${\mathbb Z}$}$/p$\mbox{${\mathbb Z}$}$ mathend000#.

Observe also the ring R mathend000# 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 $\left(\vphantom{ \begin{array}{cc} 1 & 2 \\ 0 & 3 \end{array} }\right.$$\begin{array}{cc} 1 & 2 \\ 0 & 3 \end{array}$$\left.\vphantom{ \begin{array}{cc} 1 & 2 \\ 0 & 3 \end{array} }\right)$ mathend000# 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 R = $\mbox{${\mathbb Z}$}$/6$\mbox{${\mathbb Z}$}$ mathend000# and let U = R[x] mathend000# be the ring of univariate polynomials over R mathend000#. The ring U mathend000# has units (for instance the constant polynomial 5 mathend000#), it has zero divisors (for instance the polynomial 2x + 4 mathend000# since 3(2x + 4) = 0 mathend000#) and also elements like x + 1 mathend000# 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 $\bf k$[x] mathend000# where $\bf k$ mathend000# is a field and the residue class ring $\mbox{${\mathbb Z}$}$/m$\mbox{${\mathbb Z}$}$ mathend000# (with m > 1 mathend000# not necessarily prime). The ring $\bf k$[x] mathend000# has no zero divisors whereas $\mbox{${\mathbb Z}$}$/m$\mbox{${\mathbb Z}$}$ mathend000# has zero divisors iff m mathend000# is not prime. But for every non prime m mathend000# the ring $\mbox{${\mathbb Z}$}$/m$\mbox{${\mathbb Z}$}$ mathend000# consists only of zero, units and zero divisors. This follows from the proposition below. This is why we were led to the $\mbox{${\mathbb Z}$}$/6$\mbox{${\mathbb Z}$}$[x] mathend000# example.

Proposition 1   Let E mathend000# be an Euclidean domain and m mathend000# an element of E mathend000# with m $\neq$ 0 mathend000# and m $\neq$ 1 mathend000#. Consider the residue class ring R = E/$\langle$m$\rangle$ mathend000# where $\langle$m$\rangle$ mathend000# denotes the ideal generated by m mathend000#. Then every element of R mathend000# is either zero, a zero divisor or a unit.

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

u a + v m  =  g (2)

Observe that u mod m mathend000# cannot be zero (otherwise g mod m mathend000# would be zero and m mathend000# would divide g mathend000# and thus a mathend000#). If g = 1 mathend000# then u a $\equiv$ 1 mod m mathend000# and this shows a mod m mathend000# is a unit of R mathend000#. The same result holds if g mathend000# is a unit. Assume from now on that g mathend000# is not a unit. Since g mathend000# divides a mathend000# and m mathend000# let a' mathend000# and m' mathend000# be such that

a  =  g a'    and    m  =  g m' (3)

Observe that m'mod m mathend000# is not zero (otheriwse m' mathend000# would write m' = m''m mathend000# leading to the contradiction g m'' = 1 mathend000#). We have

$$\equiv$$ (4)

This shows that a mod m mathend000# is a zero divisor of R mathend000#. Yes, this was that simple! $\qedsymbol$

Definition 1   Let n mathend000# be a positive integer and $\omega$ $\in$ R mathend000#.

1. $\omega$ mathend000# is a n mathend000#-th root of unity if $\omega^{{n}}_{{}}$ = 1 mathend000#.
2. $\omega$ mathend000# is a primitive n mathend000#-th root of unity if
   1. $\omega^{{n}}_{{}}$ = 1 mathend000#,
   2. n mathend000# is a unit in R mathend000#,
   3. for every prime divisor t mathend000# of n mathend000# the element $\omega^{{{n/t}}}_{{}}$ - 1 mathend000# is neither zero nor a zero divisor.

Remark 1   When R mathend000# is an integral domain the last condition of Definition 1 becomes: for every prime divisor t mathend000# of n mathend000# the element $\omega^{{{n/t}}}_{{}}$ $\neq$ 1 mathend000#. Observe also that a n mathend000#-th root of unity is necessarily a unit.

Example 2   Consider that R mathend000# is the field $\mbox{${\mathbb C}$}$ mathend000# of complex numbers. The number $\omega$ = e^{2 $\imath$$\pi$/8} mathend000# is a a primitive 8 mathend000#-th root of unity.

Example 3   In R = $\mbox{${\mathbb Z}$}$/8$\mbox{${\mathbb Z}$}$ mathend000# we have 3² $\equiv$ 1 mathend000#. However 3 mathend000# is not a primitive 2 mathend000#-th of unity, since n = 2 mathend000# is not a unit in R mathend000#.

Example 4   In R = $\mbox{${\mathbb Z}$}$/17$\mbox{${\mathbb Z}$}$ mathend000# 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 3 mathend000# is a primitive 16 mathend000#-th root of unity. However with $\omega$ = 2 mathend000# we have $\omega^{{8}}_{{}}$ - 1 = 0 mathend000# since (2⁴ -1)(2⁴ +1) = 15 x 17 $\equiv$ 0 mathend000#.

Lemma 1   Let 1 < $\ell$ < n mathend000# be integers and let $\omega$ mathend000# be a primitive n mathend000#-th root of unity. Then we have

1. $\omega^{{{\ell}}}_{{}}$ - 1 mathend000# is neither zero nor a zero divisor in R mathend000#,
2. $\Sigma_{{{0 \, \leq \, j \, < \, n}}}^{{}}$ $\omega^{{{j \, {\ell}}}}_{{}}$ = 0 mathend000#.

Proof. It relies on the formula

$$\Sigma_{{{0 \, \leq \, j \, < \, m}}}^{{}}$$ (5)

which holds for every c $\in$ R mathend000# and every positive integer m mathend000#.

Let us prove the first statement of the lemma. Let g mathend000# be the gcd of $\ell$ mathend000# and n mathend000#. Let u, v $\in$ $\mbox{${\mathbb Z}$}$ mathend000# be such that

$$\ell$$ (6)

Since $\ell$  <  n mathend000# we have 1  $\leq$  g  <  n mathend000#. Hence we can cancel a prime factor t mathend000# of n mathend000# such that

g  |  (n/t) (7)

Let

$$\omega^{{g}}_{{}}$$ (8)

in Relation (5) leading to

$$\omega^{{g}}_{{}} \omega^{{{n/t}}}_{{}}$$ (9)

for some a $\in$ R mathend000#. Hence if ($\omega^{{g}}_{{}}$ - 1) mathend000# would be zero or a zero divisor then so would be ($\omega^{{{n/t}}}_{{}}$ - 1) mathend000# which is false. Now applying Relation (5) with c = $\omega^{{{\ell}}}_{{}}$ mathend000# and m = u mathend000# implies that ($\omega^{{{\ell}}}_{{}}$ - 1) mathend000# divides ($\omega^{{{u \, {\ell}}}}_{{}}$ - 1) mathend000#. But with Relation (6) we obtain

$$\omega^{{{u \, {\ell}}}}_{{}} \omega^{{{u \, {\ell}}}}_{{}} \omega^{{{v \, n}}}_{{}} \omega^{{g}}_{{}}$$ (10)

Hence

$$\omega^{{{\ell}}}_{{}} \omega^{{g}}_{{}}$$ (11)

Therefore ($\omega^{{{\ell}}}_{{}}$ - 1) mathend000# cannot be zero or a zero divisor.

Now let us prove the second statement of the lemma. By applying Relation (5) with c = $\omega^{{{\ell}}}_{{}}$ mathend000# and m = n mathend000# we have

$$\omega^{{{\ell}}}_{{}} \Sigma_{{{0 \, \leq \, j \, < \, n}}}^{{}} \omega^{{{{\ell} \, j}}}_{{}} \omega^{{{{\ell} \, n}}}_{{}}$$ (12)

Since ($\omega^{{{\ell}}}_{{}}$ - 1) mathend000# is neither zero nor a zero divisor we otain the desired formula. $\qedsymbol$