AlgebraDifficulty 45-95269 tagged problems

Roots of Unity

Roots of Unity is the habit of exploiting evenly spaced complex roots to factor polynomials and filter periodic sums. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$\text{The } n\text{th roots of unity are } \omega_k = e^{2\pi i k/n}\ (k = 0, 1, \dots, n-1),\quad \sum_{k=0}^{n-1}\omega_k = 0\ (n \ge 2).$$

The solutions of $z^n = 1$ are $n$ equally spaced points on the unit circle, and (for $n \ge 2$) they sum to zero — a fact that filters periodic sums and factors polynomials.

Why It Works

1
Solve $z^n = 1$: writing $z = e^{i\theta}$ forces $e^{in\theta} = 1$, so $n\theta = 2\pi k$, giving $z = e^{2\pi i k/n}$ for $k = 0, \dots, n-1$ — $n$ points spaced $\frac{2\pi}{n}$ apart on the unit circle.
2
These are precisely the roots of $z^n - 1 = 0$, so $z^n - 1 = \prod_{k=0}^{n-1}(z - \omega_k)$.
3
By Vieta, the sum of the roots equals minus the coefficient of $z^{n-1}$ in $z^n - 1$, which is $0$ for $n \ge 2$. Hence $\sum \omega_k = 0$.
4
Equivalently the geometric series $\sum_{k=0}^{n-1}\omega^k = \frac{\omega^n - 1}{\omega - 1} = 0$ for any primitive root $\omega \ne 1$.

Worked Examples

Example 1

Let $\omega = e^{2\pi i/3}$ be a primitive cube root of unity. Evaluate $1 + \omega + \omega^2$ and then $\omega^4 + \omega^2$.

1
The cube roots of unity satisfy $z^3 - 1 = (z - 1)(z^2 + z + 1) = 0$; since $\omega \ne 1$, $\omega^2 + \omega + 1 = 0$, so $1 + \omega + \omega^2 = 0$.
2
Reduce exponents mod $3$: $\omega^4 = \omega^{3}\cdot\omega = 1\cdot\omega = \omega$.
3
So $\omega^4 + \omega^2 = \omega + \omega^2 = -1$ (from $1 + \omega + \omega^2 = 0$).

Answer:

$1 + \omega + \omega^2 = 0$ and $\omega^4 + \omega^2 = -1$.

Warm-up

Let $\omega$ be a primitive cube root of unity. Compute $(1 + \omega)(1 + \omega^2)$.

1
Expand: $(1 + \omega)(1 + \omega^2) = 1 + \omega^2 + \omega + \omega^3$.
2
Use $\omega^3 = 1$ and $1 + \omega + \omega^2 = 0$: the expression is $1 + (\omega + \omega^2) + 1 = 1 + (-1) + 1$.
3
Therefore the product equals $1$.

Answer:

$1$.

Contest level

Evaluate $\dbinom{6}{0} + \dbinom{6}{3} + \dbinom{6}{6}$ using the roots-of-unity filter.

1
With $\omega = e^{2\pi i/3}$, the filter for indices divisible by $3$ is $\dfrac{1}{3}\sum_{j=0}^{2}(1 + \omega^j)^6$, since $\frac{1}{3}\sum_j \omega^{jk}$ is $1$ when $3 \mid k$ and $0$ otherwise.
2
Evaluate each term. $(1 + 1)^6 = 64$. Because $1 + \omega = -\omega^2$, we get $(1 + \omega)^6 = (-\omega^2)^6 = \omega^{12} = 1$; similarly $(1 + \omega^2)^6 = (-\omega)^6 = \omega^6 = 1$.
3
Average: $\dfrac{64 + 1 + 1}{3} = \dfrac{66}{3} = 22$. (Direct check: $1 + 20 + 1 = 22$.)

Answer:

$22$.

Olympiad / Challenge

Let $\omega = e^{2\pi i/5}$. Compute $\displaystyle\prod_{k=1}^{4}\left(1 - \omega^k\right)$.

1
Factor $z^5 - 1 = \prod_{k=0}^{4}(z - \omega^k) = (z - 1)\prod_{k=1}^{4}(z - \omega^k)$, so $\prod_{k=1}^{4}(z - \omega^k) = \dfrac{z^5 - 1}{z - 1} = 1 + z + z^2 + z^3 + z^4$.
2
We want the product at $z = 1$, so substitute $z = 1$ into the right-hand polynomial.
3
$1 + 1 + 1 + 1 + 1 = 5$.

Answer:

$5$.

Going Deeper

Generalization: the same vanishing-sum fact powers the roots-of-unity filter $\frac{1}{n}\sum_{j=0}^{n-1} f(\omega^j x)$, which extracts the terms of a generating function whose exponents lie in a fixed residue class mod $n$ — and $\prod_{k=1}^{n-1}(1 - \omega^k) = n$ in general.
Where it appears: AIME problems summing $\binom{n}{0} + \binom{n}{m} + \binom{n}{2m} + \cdots$, factoring cyclotomic polynomials, and any periodic sum where grouping by residue collapses the count.
Pitfall: the identity $\sum_{k=0}^{n-1}\omega_k = 0$ holds for $n \ge 2$ but FAILS for $n = 1$ (where the single root is $1$). Likewise $1 + \omega + \cdots + \omega^{n-1} = 0$ requires $\omega \ne 1$ to be a root of unity; plugging in $\omega = 1$ gives $n$, not $0$ — the most common slip in filter computations.

Spot the Signal

Look for problems where the key step is exploiting evenly spaced complex roots to factor polynomials and filter periodic sums.
You can describe the hard part as exploiting evenly spaced complex roots to factor polynomials and filter periodic sums, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the expression or equation that calls for roots of unity, then rewrite the givens around it.
Name the relation that makes Roots of Unity legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Roots of Unity just because the surface looks familiar; verify the required condition first.
Applying Roots of Unity because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let roots of unity reveal the algebraic structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is exploiting evenly spaced complex roots to factor polynomials and filter periodic sums.

Back to techniques

AlgebraDifficulty 45-95269 tagged problems

Roots of Unity

Practice this technique Match my level

The Key Result

$$\text{The } n\text{th roots of unity are } \omega_k = e^{2\pi i k/n}\ (k = 0, 1, \dots, n-1),\quad \sum_{k=0}^{n-1}\omega_k = 0\ (n \ge 2).$$

The solutions of $z^n = 1$ are $n$ equally spaced points on the unit circle, and (for $n \ge 2$) they sum to zero — a fact that filters periodic sums and factors polynomials.

Why It Works

1
Solve $z^n = 1$: writing $z = e^{i\theta}$ forces $e^{in\theta} = 1$, so $n\theta = 2\pi k$, giving $z = e^{2\pi i k/n}$ for $k = 0, \dots, n-1$ — $n$ points spaced $\frac{2\pi}{n}$ apart on the unit circle.
2
These are precisely the roots of $z^n - 1 = 0$, so $z^n - 1 = \prod_{k=0}^{n-1}(z - \omega_k)$.
3
By Vieta, the sum of the roots equals minus the coefficient of $z^{n-1}$ in $z^n - 1$, which is $0$ for $n \ge 2$. Hence $\sum \omega_k = 0$.
4
Equivalently the geometric series $\sum_{k=0}^{n-1}\omega^k = \frac{\omega^n - 1}{\omega - 1} = 0$ for any primitive root $\omega \ne 1$.

Worked Examples

Example 1

Let $\omega = e^{2\pi i/3}$ be a primitive cube root of unity. Evaluate $1 + \omega + \omega^2$ and then $\omega^4 + \omega^2$.

1
The cube roots of unity satisfy $z^3 - 1 = (z - 1)(z^2 + z + 1) = 0$; since $\omega \ne 1$, $\omega^2 + \omega + 1 = 0$, so $1 + \omega + \omega^2 = 0$.
2
Reduce exponents mod $3$: $\omega^4 = \omega^{3}\cdot\omega = 1\cdot\omega = \omega$.
3
So $\omega^4 + \omega^2 = \omega + \omega^2 = -1$ (from $1 + \omega + \omega^2 = 0$).

Answer:

$1 + \omega + \omega^2 = 0$ and $\omega^4 + \omega^2 = -1$.

Warm-up

Let $\omega$ be a primitive cube root of unity. Compute $(1 + \omega)(1 + \omega^2)$.

1
Expand: $(1 + \omega)(1 + \omega^2) = 1 + \omega^2 + \omega + \omega^3$.
2
Use $\omega^3 = 1$ and $1 + \omega + \omega^2 = 0$: the expression is $1 + (\omega + \omega^2) + 1 = 1 + (-1) + 1$.
3
Therefore the product equals $1$.

Answer:

$1$.

Contest level

Evaluate $\dbinom{6}{0} + \dbinom{6}{3} + \dbinom{6}{6}$ using the roots-of-unity filter.

1
With $\omega = e^{2\pi i/3}$, the filter for indices divisible by $3$ is $\dfrac{1}{3}\sum_{j=0}^{2}(1 + \omega^j)^6$, since $\frac{1}{3}\sum_j \omega^{jk}$ is $1$ when $3 \mid k$ and $0$ otherwise.
2
Evaluate each term. $(1 + 1)^6 = 64$. Because $1 + \omega = -\omega^2$, we get $(1 + \omega)^6 = (-\omega^2)^6 = \omega^{12} = 1$; similarly $(1 + \omega^2)^6 = (-\omega)^6 = \omega^6 = 1$.
3
Average: $\dfrac{64 + 1 + 1}{3} = \dfrac{66}{3} = 22$. (Direct check: $1 + 20 + 1 = 22$.)

Answer:

$22$.

Olympiad / Challenge

Let $\omega = e^{2\pi i/5}$. Compute $\displaystyle\prod_{k=1}^{4}\left(1 - \omega^k\right)$.

1
Factor $z^5 - 1 = \prod_{k=0}^{4}(z - \omega^k) = (z - 1)\prod_{k=1}^{4}(z - \omega^k)$, so $\prod_{k=1}^{4}(z - \omega^k) = \dfrac{z^5 - 1}{z - 1} = 1 + z + z^2 + z^3 + z^4$.
2
We want the product at $z = 1$, so substitute $z = 1$ into the right-hand polynomial.
3
$1 + 1 + 1 + 1 + 1 = 5$.

Answer:

$5$.

Going Deeper

Generalization: the same vanishing-sum fact powers the roots-of-unity filter $\frac{1}{n}\sum_{j=0}^{n-1} f(\omega^j x)$, which extracts the terms of a generating function whose exponents lie in a fixed residue class mod $n$ — and $\prod_{k=1}^{n-1}(1 - \omega^k) = n$ in general.
Where it appears: AIME problems summing $\binom{n}{0} + \binom{n}{m} + \binom{n}{2m} + \cdots$, factoring cyclotomic polynomials, and any periodic sum where grouping by residue collapses the count.
Pitfall: the identity $\sum_{k=0}^{n-1}\omega_k = 0$ holds for $n \ge 2$ but FAILS for $n = 1$ (where the single root is $1$). Likewise $1 + \omega + \cdots + \omega^{n-1} = 0$ requires $\omega \ne 1$ to be a root of unity; plugging in $\omega = 1$ gives $n$, not $0$ — the most common slip in filter computations.

Spot the Signal

Look for problems where the key step is exploiting evenly spaced complex roots to factor polynomials and filter periodic sums.
You can describe the hard part as exploiting evenly spaced complex roots to factor polynomials and filter periodic sums, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the expression or equation that calls for roots of unity, then rewrite the givens around it.
Name the relation that makes Roots of Unity legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Roots of Unity just because the surface looks familiar; verify the required condition first.
Applying Roots of Unity because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let roots of unity reveal the algebraic structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is exploiting evenly spaced complex roots to factor polynomials and filter periodic sums.