Root of unity

An nth root of unity is a solution of zⁿ = 1: the n points ζ⁰, ζ¹, …, ζⁿ⁻¹ spaced evenly around the unit circle, where ζ = e^(2πi/n). They are the algebraic form of a thing that wraps — a heading that turns by a fixed angle, a socket on a ring, a residue modulo a prime. The reason they keep appearing in the problems below is not that any of them is about complex numbers. It is that each one asks a question about a cyclic structure, and roots of unity turn that question into polynomial arithmetic with exact integer answers.

The idea

The nth roots of unity form a cyclic group of order n under multiplication, generated by any ζᵏ with gcd(k, n) = 1 — the primitive ones, of which there are φ(n). That group is the same abstract object as ℤ/nℤ under addition, which is why "socket k of n" and "ζᵏ" are interchangeable descriptions of the same thing.

What makes them computationally useful is that we know exactly which linear relations hold between them. Over the rationals, the minimal polynomial of a primitive nth root is the cyclotomic polynomial Φₙ, of degree φ(n) and with integer coefficients, and

xⁿ - 1 = ∏_{d | n} Φ_d(x)

For a prime p, Φ_p = 1 + x + … + x^(p-1), which says the p distinct pth roots sum to zero and — crucially — that this is the only relation among them. So a question of the form "does this sum of roots of unity vanish?" is never a numerical question. Encode a subset S ⊆ {0, …, n-1} as the 0/1 polynomial f_S(x) = Σ_{k∈S} xᵏ; then

Σ_{k∈S} ζᵏ = 0   ⟺   Φₙ(x) divides f_S(x)

That equivalence is the whole subject in one line. Geometry on the left, exact integer algebra on the right.

Vanishing sums

Problem 208 is the cleanest instance. A robot walks 72° arcs, choosing left or right each step, and must return to where it started. Because every turn rotates the heading by ±72°, only five directions ever occur, and they are the fifth roots of unity. Their only rational relation is v₀ + v₁ + v₂ + v₃ + v₄ = 0, so a non-negative integer combination Σ mᵢvᵢ vanishes if and only if all five multiplicities are equal. The closure condition — a statement about a position in the plane — collapses to "each of the five directions is used the same number of times", which is a counting problem a dynamic program can walk directly. Note what was bought: no coordinates, no floating point, and an immediate corollary that the arc count must be a multiple of five.

Problem 768 is the same equivalence at the other end of the difficulty range. Candles in a ring of n sockets balance exactly when their unit vectors cancel, so f(n, m) counts the m-subsets with Φₙ | f_S. The obvious guess is that a balanced set must be a disjoint union of regular p-gons {j, j + n/p, …} for primes p | n. That guess is a theorem (Lam and Leung) when n has at most two distinct prime factors — and false as soon as it has three. In ℤ₃₀ there are balanced 6-subsets containing no complete polygon at all: the four non-trivial fifth roots sum to −1, the negatives of the two non-trivial cube roots sum to +1, and the six cancel. Any method that pattern- matches on polygons silently undercounts; a method that asks the algebraic question gets the exotic configurations for free.

Two structural facts make the algebraic question cheap, and both are worth knowing on their own:

  • Layering. With r = rad(n) the radical and t = n/r, we have Φₙ(x) = Φ_r(xᵗ). Splitting the sockets by residue mod t therefore decomposes any balanced arrangement into t independent balanced subsets of ℤ_r. The problem stops depending on n except through its radical, and the t layers combine by raising one generating function to the tth power.
  • Exact coordinates. ℤ[ζ_r] is free of rank φ(r), so each socket is a small integer vector and "balanced" is "the vectors sum to the zero vector". The basis relation on each prime axis is ζ_p^(p-1) = -(1 + ζ_p + … + ζ_p^(p-2)), i.e. the last residue maps to the all-−1 vector. This is an exact test with none of the tolerance guesswork a floating-point sum of unit vectors would need.

There is a neat packing trick on top of the second point. If a subset has at most r elements, every coordinate of its sum stays in [-r, r], so choosing a base B > 2r lets you store the whole φ(r)-vector as a single integer with no carries between coordinates. Vector addition becomes integer addition, and the balance test becomes == 0.

Roots of unity modulo p

The same group turns up in a completely different setting, and recognising it is worth more than any individual trick. The multiplicative group (ℤ/pℤ)* is cyclic of order p - 1, so the solutions of uʳ = 1 (mod p) are the unique subgroup of order gcd(r, p-1) — there are exactly that many, never more, never fewer.

Problem 421 runs on that count. Asked for the prime factors of n¹⁵ + 1, you exchange the order of summation and ask, per prime, how many n ≤ N satisfy n¹⁵ ≡ -1. Since (-1)¹⁵ = -1, those n are precisely the negatives of the 15th roots of unity mod p, so their number is d = gcd(15, p-1) ∈ {1, 3, 5, 15} — decided by two cheap congruence tests, p ≡ 1 (mod 3) and p ≡ 1 (mod 5). The fact that d is never zero is exactly why n¹⁵ + 1 is composite for every n > 1 in the first place. A factorisation problem becomes a residue-class census.

Producing the roots is textbook and worth having in your fingers:

g = pow(a, (p - 1) // r, p)   # g^r == 1 by Fermat, for any base a
                              # g == 1 means a was an r-th power — retry with the next a
roots = [pow(g, i, p) for i in range(r)]

A share (r-1)/r of bases work, so a = 2 almost always suffices. And because a cyclic group of order 15 is the internal direct product of its subgroups of orders 3 and 5, the 15th roots need no exponentiation of their own — they are the products ω^i τ^j of the cube roots and fifth roots.

From a prime to any modulus

Problem 271 asks the same question with the prime replaced by a huge composite: sum every non-trivial x < n with x³ ≡ 1 (mod n). The modulus is a primorial, 2 · 3 · 5 ⋯ 43, and that is the hint. The prime picture extends to any modulus in three steps, and the 3-and-5 split above is the first of them seen inside a single group:

  • The CRT splits the group. For n = ∏ qᵢ with coprime prime powers qᵢ, the Chinese remainder theorem gives (ℤ/nℤ)* ≅ ∏ (ℤ/qᵢℤ)*, so an rth root of unity mod n is exactly a choice of one root mod each qᵢ. The roots form a product set and their count is multiplicative. For cube roots, each prime p ≡ 1 (mod 3) triples the count and every other prime contributes only x = 1, so fourteen prime factors collapse to 3ᵗ combinations over the t productive ones — the whole cost is factoring n.
  • Hensel lifts a prime to its powers. When p ∤ r, the derivative r·x^(r-1) is a unit, so Hensel's lemma lifts each root mod p uniquely to pᵏ by the Newton step x ← x − (xʳ − 1)·(r·x^(r−1))⁻¹, and the count stays gcd(r, p − 1). When p | r the lemma's hypothesis fails and the count genuinely changes: mod 3 the only cube root of unity is 1, but mod 3ᵏ for k ≥ 2 there are three — 1, 1 + 3^(k−1), 1 + 2·3^(k−1) — because (ℤ/3ᵏℤ)* is cyclic of order 2·3^(k−1). The general rule for odd p is still "count = gcd(r, |group|)", with |group| = φ(pᵏ); it is only the shortcut gcd(r, p − 1) that breaks. (Powers of 2 are their own case: (ℤ/2ᵏℤ)* is not cyclic.)
  • Idempotents do the combining. Precompute, per factor, eᵢ ≡ 1 (mod qᵢ) and ≡ 0 modulo every other factor; then each root is Σ rᵢ eᵢ mod n, and enumerating the product is a list of partial sums grown factor by factor, each entry branching into one or three.

One pitfall is specific to the composite case. The problem asks for a sum of integers, and with hundreds of roots each below n that sum far exceeds n, so summing the CRT combinations modulo n gives only S(n) mod n. Reduce each root to its representative in [0, n), then add the representatives in exact (big or 128-bit) arithmetic.

The roots-of-unity filter

One more use, and the one most engineers meet first. Summing a function over all nth roots of unity annihilates everything whose index is not a multiple of n, because Σ_j ζ^(jk) is n when n | k and 0 otherwise. That gives the filter

Σ_{n | k} a_k = (1/n) · Σ_{j=0}^{n-1} A(ζʲ)

for a generating function A. It is the finite-group version of "take only every nth term", it is the reason FFT works, and it is the standard way to answer "how many of these have total ≡ 0 mod n" without an n-slot table.

How to reason about it

  • The tell is a cyclic structure, not a complex number: a heading that turns by a fixed angle, a position on a ring, an exponent taken mod something, or a count you need modulo n. If the object wraps, ℤ/nℤ is in play and its character group is the roots of unity.
  • Never sum unit vectors in floating point. The whole value of the subject is that vanishing is decidable exactly. Work in ℤ[ζ] coordinates, or with Φₙ-divisibility, or in ℤ[x]/(xⁿ - 1). A near-zero double tells you nothing, and the exotic cancellations are precisely where it will mislead you.
  • Know which relations exist. For prime n, only the all-roots sum. For composite n, Φₙ is the complete answer and the polygon intuition is a sufficient condition masquerading as a necessary one — safe for at most two distinct primes, wrong beyond that.
  • Reduce to the radical. Φₙ(x) = Φ_r(xᵗ) means the hard work only ever scales with rad(n), and repeated prime factors cost you t independent copies of a smaller problem rather than a bigger one.
  • Mod p, the count is gcd(r, p-1). No search, no factorisation of p - 1, and the generator is one modular exponentiation away.
  • Mod composite n, factor first. The CRT makes the roots a product over prime powers, Hensel carries each prime to its powers, and the only place to stop and think is a prime dividing r (or the prime 2), where the count is not the one the prime suggests.

Problems6 / 6

  • ● 0208 — Robot Walks
  • ● 0271 — Modular Cubes, Part 1
  • ● 0421 — Prime Factors of $n^{15}+1$
  • ● 0635 — Subset Sums
  • ● 0768 — Chandelier
  • ● 0971 — Modular Polynomial Composition