Modular arithmetic & roots of unity

A pattern hides inside numbers — and a quantum machine finds it.

Here's something that looks like magic at first. Take the number 2 and keep multiplying it by itself, but after each step, ask: what's the remainder when you divide by 5?

This isn't a coincidence. It's a consequence of arithmetic that wraps around like a clock — that's called modular arithmetic. That repeating period (the number 4 here) is exactly what Shor's algorithm is designed to find — and finding it efficiently is what makes it exponentially faster than any classical computer.

The clock idea — numbers that wrap around and repeat.

What "mod" means — start with the intuition

Think of a clock with $N$ positions, labeled 0 through $N-1$. You start at 0. You take $a$ steps forward. Where do you land? That's exactly what modular arithmetic computes. Formally, $a \bmod N$ is the remainder when $a$ is divided by $N$:

$$a \bmod N = r \quad \text{where} \quad a = q \cdot N + r, \quad 0 \le r < N$$

Here $q$ is the quotient — how many full loops you've completed — and $r$ is the remainder: how many extra steps you took after the last full loop. The remainder $r$ always falls between $0$ and $N-1$. It's your position on the clock.

Try a few — the pattern will become instinct

The key property — cycles are unavoidable

Here's what makes modular arithmetic so special for quantum computing: it always cycles. With only $N$ possible values (0 through $N-1$), any sequence must eventually repeat. Try starting at 0 and adding 3 each time, with $N = 7$:

$0, 3, 6, 2, 5, 1, 4, 0, 3, 6, 2, \ldots$

After 7 steps you're back at 0. The cycle has period 7. This isn't a coincidence — there are only $N$ possible remainders, so any sequence must repeat before taking more than $N$ steps. This guaranteed cycling is the core structure Shor's algorithm exploits.

Dots on a circle — the clock idea, dressed in complex numbers.

What is a root of unity?

A complex number $z$ is called an $N$-th root of unity if $z^N = 1$. There are exactly $N$ of them, and they all live on the unit circle (the circle of radius 1). The most important one is the primitive $N$-th root of unity:

$$\omega_N = e^{2\pi i / N}$$

Think of it as a rotation: $\omega_N$ starts at the point $(1, 0)$ on the complex plane and is rotated $\tfrac{2\pi}{N}$ radians counterclockwise — exactly one $N$-th of a full turn. Its powers step through $N$ equally spaced positions:

$$\omega_N^k = e^{2\pi i k / N}$$

These $N$ points divide the circle into $N$ equal arcs — like hour marks on a clock, but on the complex unit circle. Together they form the complete set of $N$-th roots of unity: every complex number $z$ satisfying $z^N = 1$.

Geometric picture

Proving it: $\omega_N^N = 1$ (step by step, no gaps)

The beautiful connection — clock arithmetic and circle rotations are the same thing

Here's the insight that ties everything together. Both systems — mod $N$ arithmetic and $N$-th roots of unity — are the same abstract cycle, just written in different languages.

In mod $N$: add 1 to move forward; add $N$ to wrap back to start. In roots of unity: multiply by $\omega_N$ to move forward; multiply by $\omega_N^N = 1$ to wrap back. The dictionary between them is simple: the integer $k$ on the clock corresponds to the complex number $\omega_N^k$ on the circle.

Micro practice — three conceptual checks

Three tools to make it real — feel the clock, see the circle, watch the cycle.

Start with Tool 1 to feel modular arithmetic with your own numbers. Then use Tool 2 to see how those numbers place points on a circle. Finally, use Tool 3 to watch multiplication by $\omega_N$ step through the cycle one position at a time.