Orthogonality of Roots of Unity

Last updated on Apr 21, 2026

The sum of powers of the $k$ -th roots of unity generated by a primitive $k$ -th root of unity is either zero or $k$ . We call this property the orthogonality of roots of unity. We will directly leverage this property in the next chapter.

We first illustrate this property through examples, so the reader becomes familiar with it. Then we will prove it in general.

The sum of powers of roots of unity

Consider the $k$ -th roots of unity generated by a primitive $k$ -th root of unity $\omega$ :

[ 1, \omega, \omega^2, ..., \omega^{k-1} ]

If we take this list of elements and raise each element to a power $m$ , we obtain another list:

[ 1^m, \omega^m, (\omega^2)^m, ..., (\omega^{k-1})^m]

The goal of this chapter is to show what happens when we sum all the elements of this new list. In other words, we want to calculate the value of the sum $s$ below for any $m$ :

s = 1^m + \omega^m + (\omega^2)^m + ... + (\omega^{k-1})^m

Consider the $4$ th roots of unity in $\mathbb{F}_{17}$ (though any field with a primitive $4$ th root of unity would work). For a primitive root $\omega$ , these roots are

[1, \omega^1, \omega^2, \omega^3],

or, using that $\omega^2 \equiv -1$ in this case, they are

[ 1, \omega, -1, -\omega ]

Let us raise these elements to some exponent $m$ , say $m=3$ :

[ 1^3, \omega^3, (-1)^3, (-\omega)^3 ]

We can simplify some of these elements by noting that $(-1)^3 = -1$ and $(-\omega)^3 = - \omega^3$ .

Thus, the same list can be written as

[ 1, \omega^3, -1, -\omega^3 ]

The sum of these elements is zero, since

1 + \omega^3 + (-1) + (-\omega^3) = 0

As another example, let us start with the 4th roots of unity in $\mathbb{F}_{17}$ again, but now raise each element to the power of 8.

This yields the following elements:

[ 1^8, \omega^8, (-1)^8, (-\omega)^8 ]

Since $8$ is even, we have $(-1)^8 = 1$ and $(-\omega)^8 = \omega^8$ .

Also, remember that for the $4$ th roots of unity, $\omega^4=1$ . Thus, $\omega^8 = (\omega^4)^2 = 1^2 = 1$ .

Therefore, our list simplifies to

[ 1^8=1, \omega^8=1, 1^8=1, \omega^8=1 ]

The sum of the elements is

s=1 + 1+1+1=4

In the examples above, when $m$ is not a multiple of $k$ $(k=4,m=3)$ , the sum is zero, but when $m$ is a multiple of $k$ ( $k=4,m=8$ ), the sum is $k$ . This is true in general.

We will show and prove the following:

If the power $m$ is not a multiple of $k$ , the sum is zero.
Otherwise, if $m$ is a multiple of $k$ , the sum is $k$ .

Before proving this fact in general, let us see one more example.

8th roots of unity in $\mathbb{F}_{17}$

Consider the $8$ th roots of unity in $\mathbb{F}_{17}$ . They can be written as

[ 1, \omega, \omega^2, \omega^3, -1, -\omega, -\omega^2, - \omega^3 ],

where we used that $\omega^4 \equiv -1$ for a primitive $8$ th root of unity $\omega$ .

If we raise each element of this list to a power $m$ that is not a multiple of $8$ and sum all the elements, the result is zero. Otherwise, if $m$ is a multiple of $8$ , the sum is $8$ .

The new list is given by

[1^m, \omega^m, (\omega^{2})^m, (\omega^3)^m, (-1)^m, (-\omega)^m, (-\omega^{2})^m, (-\omega^3)^m ]

Let us check the possible cases.

Case 1: $m$ is not a multiple of $8$

Let us consider the case $m=2$ . The list is

[ 1^2, \omega^2, (\omega^2)^2, (\omega^3)^2, (-1)^2, (-\omega)^2,(-\omega^2)^2, (-\omega^3)^2 ]

It can be written as

[1, \omega^2, \omega^4, \omega^6, 1, \omega^2, \omega^4, \omega^6 ]

Using the fact that $\omega^4 \equiv -1$ , the list becomes

[1, \omega^2, -1, -\omega^2, 1, \omega^2, -1, -\omega^2 ]

Summing these elements, we obtain

\begin{aligned} s &= 1 + \omega^2 + (-1) + (-\omega^2) + 1 + \omega^2 + (-1) + (-\omega^2) \\ &= (1 - 1) + (\omega^2 - \omega^2) + (1 - 1) + (\omega^2 - \omega^2) \\ &= 0 \end{aligned}

Exercise: Show that the sum vanishes for $m=3$ and $m=4$ .

Case 2: $m$ is a multiple of 8

Let us consider the case where $m=16$ . Then we obtain the new list

[1^{16}, \omega^{16}, (\omega^2)^{16}, (\omega^3)^{16}, (-1)^{16}, (-\omega)^{16}, (-\omega^2)^{16}, (-\omega^3)^{16} ],

[1, \omega^{16}, \omega^{32}, \omega^{48}, 1, \omega^{16}, \omega^{32}, \omega^{48} ]

We also have that:

\begin{aligned} \omega^{16} &= (\omega^8)^2 \\ \omega^{32} &= (\omega^8)^4 \\ \omega^{48} &= (\omega^8)^6 \end{aligned}

Since we know that $\omega^{8} \equiv 1$ for any primitive 8th root of unity, the list is actually

[1,1^2,1^4,1^6,1,1^2,1^4,1^6]

and the sum of all terms is $8$ .

Sum of the powers of the $k$ -th roots of unity

Now let us prove in general what we have shown through examples.

Theorem. Consider all the $k$ -th roots of unity generated by a primitive $k$ -th root of unity $\omega$ . The sum of the powers of these $k$ -th roots of unity is:

zero if the power is not a multiple of $k$ ;
$k$ if the power is a multiple of $k$ .

Below, we will prove the two cases separately.

Case (1): Proof that the sum is zero when the exponent is not a multiple of $k$

Consider the $k$ -th roots of unity, each raised to a power $m$ that is not a multiple of $k$ :

[ (\omega^0)^m, (\omega^1)^m, (\omega^2)^m, ..., (\omega^{k-1})^m ]

We want to calculate the sum

s = (\omega^0)^m + (\omega^1)^m + (\omega^2)^m + ... + (\omega^{k-1})^m

This sum can be written as

s = \sum_{i=0}^{k-1} (\omega^{i})^m

We can use the fact that $(\omega^i)^m = (\omega^m)^i$ to rewrite the sum as

s = \sum_{i=0}^{k-1} (\omega^{m})^i

The formula above is a geometric series, that is, a sum of successive powers of the same element:

s = (\omega^m)^0 + (\omega^m)^1 + (\omega^m)^2 + ... + (\omega^m)^{k-1}

A geometric series of this form satisfies

s = (\omega^m)^0 + (\omega^m)^1 + (\omega^m)^2 + ... + (\omega^m)^{k-1} = \frac{(\omega^m)^k - 1}{\omega^m -1}

To prove that the above fraction equals zero, we must first show that the denominator is non-zero and then that the numerator equals zero.

The fact that $m$ is not a multiple of $k$ is crucial here. Recall the definition of a primitive $k$ -th root of unity: it is an element $\omega$ such that $\omega^k \equiv 1$ , but $\omega^r \neq 1$ for any $0 \leq r <k$ .

Thus, for primitive $k$ -th roots of unity $\omega$ , only powers of $\omega^k$ are equal to $1$ , such as $(\omega^k)^0, (\omega^k)^1, (\omega^k)^2$ , and so on.

Since $m$ is not a multiple of $k$ , $\omega^m$ is not of the form $\omega^{nk}$ for any integer $n$ , and therefore $\omega^m \neq 1$ . Thus, the denominator $\omega^m-1$ of the fraction above is nonzero.

Let us now consider the numerator $(\omega^m)^k - 1$ . It can be written as $(\omega^k)^m - 1$ .

Since $\omega$ is a primitive $k$ -th root of unity, we have $\omega^k = 1$ , and the numerator becomes

\begin{align*} (\omega^k)^m -1 &=(1)^m-1 \\ &= 1 - 1 \\ &= 0 \end{align*}

Since the numerator is zero and the denominator is nonzero, the entire sum is zero.

In the next section, we will study the case where the exponent $m$ is a multiple of $k$ .

Case (2): Raising each element by an exponent that is a multiple of $k$

In this section, we will show that the sum of the $k$ -th roots of unity raised to a power $m$ that is a multiple of $k$ is not zero, but rather $k$ .

Consider the $k$ -th roots of unity

[ \omega^0, \omega^1, \omega^2, ..., \omega^{k-1} ]

Let us raise each element in this list to some power $m$ :

[ (\omega^0)^m, (\omega^1)^m, (\omega^2)^m, ..., (\omega^{k-1})^m ]

Since $(a^b)^c = (a^c)^b$ , we can rearrange each term above as follows:

[ (\omega^m)^0, (\omega^m)^1, (\omega^m)^2, ..., (\omega^m)^{k-1} ]

Now consider the case in which $m$ is a multiple of $k$ , that is, $m=kn$ for some $n$ . Thus, our list can be written as

[ (\omega^{nk})^0, (\omega^{nk})^1, (\omega^{nk})^2, ..., (\omega^{nk})^{k-1} ]

Since $\omega^{nk} = (\omega^k)^n$ , we obtain the list

[ (\omega^{k})^{0n}, (\omega^{k})^{1n}, (\omega^{k})^{2n},..., (\omega^{k})^{(k-1)n}]

Using $\omega^k \equiv 1$ , the list consists of the number 1 raised to some power:

[ (1)^{0n}, (1)^{1n}, (1)^{2n},..., (1)^{(k-1)n}]

or simply

[1,1,1,...,1]

Since there are $k$ elements in the list, the sum is

\underbrace{1 + 1 + 1 + \dots + 1}_{k \text{ times}} = k

Combining the two properties

An elegant and convenient way to express both properties is the following:

\sum_{i=0}^{k-1} (\omega^{i})^{m}=\begin{cases}k, & \text{if } m \text{ is a multiple of } k,\\[6pt]0, & \text{otherwise}.\end{cases}

Here the summation ranges from the first term, $\omega^0$ , to the last, $\omega^{k-1}$ .

The inner product of two lists of $k$ -th roots of unity

In this section, we will rewrite our relation obtained above in a form that is more suitable for use in the following chapters.

More precisely, we will write it as

\sum_{i=0}^{k-1} (\omega^{i})^{r-s}=\begin{cases}k, & \text{if } r\equiv s \pmod{k},\\[6pt]0, & \text{otherwise}.\end{cases}

First, let us show that these two forms are the same, and then motivate the second one.

The two forms are equivalent

If $r$ is congruent to $s$ mod $k$ (second form), then $r-s = nk$ for some integer $n$ .

Thus, we are saying that $r-s$ , which in the first form is written as $m$ , is a multiple of $k$ . This is the same as stating that $m$ is a multiple of $k$ .

The reason for using $r$ and $s$ in the second form is that we will consider the inner product of two vectors, each consisting of powers of the roots of unity.

The inner product of two vectors of roots of unity

Let us consider two vectors of $k$ -th roots of unity. The first vector, $A$ , is raised to the power $r$ and has the form

A =[ (\omega^0)^r, \omega^r, (\omega^2)^r, ..., (\omega^{k-1})^r ]

The second vector, $B$ , is raised to the negative exponent $-s$ and has the form

B = [ (\omega^0)^{-s}, \omega^{-s}, (\omega^2)^{-s}, ..., (\omega^{k-1})^{-s} ]

Note: Raising the primitive $k$ -th root of unity to a negative power is not a problem. We can write $\omega^{-s} = (\omega^{-1})^s$ , where $\omega^{-1}$ is the multiplicative inverse of $\omega.$

Since $\omega^{k} = 1$ , multiplying both sides by $\omega^{-1}$ gives $\omega^{-1} = \omega^{k-1}$ . Raising both sides to the power $s$ , we obtain $\omega^{-s} = \omega^{(k-1)s}$ .

The inner product of vectors $A$ and $B$ is

A \cdot B = (\omega^0)^r \cdot (\omega^0)^{-s} + \omega^r \cdot \omega^{-s} + ... + (\omega^{k-1})^r (\omega^{k-1})^{-s}

Equivalently, this can be written as

A \cdot B = (\omega^0)^{r-s} + \omega^{r-s} + ... + (\omega^{k-1})^{r-s}

In a compact notation, the inner product of $A$ and $B$ can be written as

A \cdot B = \sum_{i=0}^{k-1} (\omega^{i})^{r-s}

Therefore, the formula

\sum_{i=0}^{k-1} (\omega^{i})^{r-s}=\begin{cases}k, & \text{if } r\equiv s \pmod{k},\\[6pt]0, & \text{otherwise}.\end{cases}

can be understood as follows: the inner product of two vectors whose entries are powers of $k$ -th roots of unity is either $k$ or zero, depending on whether the exponents $r$ and $s$ are congruent modulo $k$ . We will use this fact in the following chapters.

This article is part of a series on the Number Theoretic Transform in our ZK Book