Roots of unity ω have the property ω^(k/2) ≡ −1

In previous articles, we established that in the finite field $\mathbb{F}_q$, if $k$ divides $q-1$:

• There exists a unique subgroup of order $k$ - the $k$-th roots of unity.
• A generator $\omega$ of this subgroup is a primitive $k$-th root of unity and is given by $\omega = g^{\frac{q-1}{k}}$, where $g$ is a generator of $\mathbb{F}_q^*$.
• $k$ is the smallest positive integer for which $\omega^k\equiv 1$.

In this article, we explore a key property of a primitive root of unity $\omega$ in $\mathbb{F}_q$: As long as $k$ is even, $\omega^{\frac{k}{2}}$ is congruent to $-1$.

Motivation

For some applications, we want to find relationships among different $k$-th roots of unity for some $k$. More precisely, we want to determine which roots of unity are additive inverses of others.

In a field $\mathbb{F}_q$, if $k$ divides $q-1$, the $k$-th roots of unity can be written as

where $\omega$ is a primitive $k$-th root of unity.

One might ask: can we easily find $-\omega$ or $- \omega^2$? Yes, we can. Let’s take the following fact, which we will prove shortly: If $k$ is even, then $\omega^\frac{k}{2} \equiv -1$.

Let us use this fact. Since $-\omega$ is the same as $(-1) \omega$, knowing that $-1 \equiv \omega^\frac{k}{2}$, we have that

The same can be used to find $- \omega^2$. We have that

This can be generalized by any $i$ as

This establishes a relationship between the $k$-th roots of unity.

As an example, let us consider the 8th roots of unity,

Using the relationship obtained, the 8th roots of unity can be written as

For this to hold, we just need to show that $\omega^\frac{k}{2} \equiv -1$ for any $k$. Let’s proceed to do that now.

What is the meaning of $-1$ in a finite field $\mathbb{F}_q$

In $\mathbb{F}_q$, the notation $-a$ denotes the additive inverse of $a$, satisfying $a + (-a) = 0$.

For example, in $\mathbb{F}_7$, since $6+1 = 7\equiv 0\pmod{7}$, we say $6$ is the additive inverse of $1$, and write

For any finite field $\mathbb{F}_q$, since $(q-1) + 1 = q \equiv 0\pmod{q}$, the additive inverse of $1$ is always $q-1$:

Let’s now look at examples of $\omega^{\frac{k}{2}}$.

Example of $\omega^{\frac{k}{2}}$ among the $k$-th roots of unity in $\mathbb{F}_{17}$

In the following examples, we use the generator $g =3$ for the multiplicative group $\mathbb{F}_{17}^*$. Since $16$ is the additive inverse of $1$ in $\mathbb{F}_{17}$, we have:

Case $k=4$

A primitive 4th root of unity is $\omega = g^{\frac{q-1}{k}} = g^{\frac{16}{4}} = 3^4 \equiv 13\pmod{17}$.

Here, $\omega^{\frac{k}{2}} = \omega^{\frac{4}{2}} = \omega^2 = 13^2\equiv 16 \equiv -1$.

Thus, we conclude that $\omega^{\frac{k}{2}} \equiv -1$ for $k=4$.

Case $k = 8$

Now $\omega = g^{\frac{q-1}{k}} = g^{\frac{16}{8}} = 3^2 \equiv 9\pmod{17}$ is a primitive 8th root of unity.

For $k=8$, $\frac{k}{2} = 4$, and we have $\omega^{\frac{k}{2}} = 9^4\equiv 16 \equiv -1$.

Example of $\omega^{\frac{k}{2}}$ among the $k$-th roots of unity in $\mathbb{F}_{97}$

In the finite field $\mathbb{F}_{97}$, we have $q-1 = 97-1 = 96$. The additive inverse of $1$ is:

The element $g = 5$ is a generator of the multiplicative group $\mathbb{F}_{97}^* = \{1,2,\dots,96\}$. The galois library provides a convenient way to find this generator using the primitive_element property, as shown below:

import galois
GF = galois.GF(97) # Define the field
GF.primitive_element # Returns GF(5, order=97)

For $k=32$, we obtain $\omega$ as

Letting $\frac{k}{2} = 16$, we calculate $\omega^{\frac{k}{2}} = 28^{16}$ with the following Python code:

result = 28**16 % 97
print(f"28^16 % 97 = {result}")  # Output: 96

Thus:

We conclude that, for $k = 32$, $\omega^{\frac{k}{2}} \equiv -1$ in $\mathbb{F}_{97}$.

Python code

The following Python code checks if $\omega^\frac{k}{2} \equiv - 1$ for a field $\mathbb{F}_q$. It is used to test this property in $\mathbb{F}_{17}$ for $k = 8$ and $\omega = 9$. You can test it for $k = 32$ with $\omega = 28$ in $\mathbb{F}_{97}$ or another valid combination of your choice.

import galois

def check_omega_half_is_minus_one(q, omega, k):
	GF = [galois.GF](http://galois.gf/)(q)
	if k % 2 != 0:
		raise ValueError("k must be even")

	omega_half = GF(omega) ** (k // 2)

	return omega_half == GF(q-1)

# Example usage:
q = 17
k = 8
omega = 9
result = check_omega_half_is_minus_one(q, omega, k)
print(f"For ω={omega} and k={k}: ω^(k/2) == -1 is {result} in F_{q}")

The mathematical proof

Let $g$ be a generator of $\mathbb{F}_q^*$. This equivalently means that $g$ is a primitive $(q-1)$-th root of unity.

Let $\omega=g^\frac{q-1}{k}$ be a primitive $k$-th root of unity in the finite field $\mathbb{F}_q$. We will prove that $\omega^{\frac{k}{2}} \equiv -1$.

The idea of the proof is to show that $\omega^\frac{k}{2}$ can only be $1$ or $−1$. We will exclude the possibility that $\omega^\frac{k}{2}$ is $1$, leaving $−1$ as the only option.

Proof:

Let’s take the square of $\omega^\frac{k}{2}$. It is given by

The last equality follows from the fact that $\omega$ is a primitive $k$-th root of unity.

Since the square of $\omega^\frac{k}{2}$ is $1$, that is, $\left(\omega^\frac{k}{2} \right)^2 \equiv 1$, then $\omega^\frac{k}{2}$ can only be $1$ or $-1$, because only $1^2$ or $(-1)^2$ is equal to $1$.

Let us show that it cannot be $1$.

Replace $\omega = g^{\frac{q-1}{k}}$ into $\omega^{\frac{k}{2}}$. This gives us that

Since $g$ is a primitive $(q-1)$-th root of unity, the smallest positive integer $r$ for which $g^r\equiv 1$ is $r=q−1$.

In other words, there is no integer $r$ smaller than $q-1$ such that $g^{r} \equiv 1$. Since $\frac{q-1}{2} < q-1$, $g^{\frac{q-1}{2}}$ cannot be $1$. Therefore, the only possibility is that $\omega^\frac{k}{2}$ is equal to $-1$.

Summary

• If $\omega$ is a primitive $k$-th root of unity in a finite field $\mathbb{F}_q$, then $\omega^{\frac{k}{2}} \equiv -1$ for even $k$.
• Using this property, we have that $- \omega^i = \omega^{\frac{k}{2}+i}$ or stated equivalently, $\omega^i$ is the additive inverse of $\omega^{k/2+i}$.

The following chapter will introduce a visualization that makes these points easier to remember.