Modular Arithmetic

Of everything in this track, this is the one idea everything else sits on top of. Every ZK proof system, every elliptic curve, every Circom circuit runs its arithmetic inside a modulus — and the surprising part is that you already use the same idea daily, just under a more familiar name.

The clock analogy

A clock only has 12 hours on its face. Past 12, it doesn’t keep counting up to 13 — it wraps back to 1. If it’s 9:00 and 4 hours pass, the clock doesn’t read 13:00, it reads 1:00:

Fig. 1 — the hand never reaches 13. It wraps back around to 1.

A familiar wraparound

$9 + 4 = 13 \equiv 1 \pmod{12}$

The number you wrap around — $12$ , for a clock — is called the modulus. In a ZK proof system, the modulus is a single, enormous prime number, but the wraparound behaves exactly the same way.

The mod operation

Formally, the mod operation gives you the remainder left over after dividing by the modulus. It’s worth seeing the same sum three ways, so the difference from plain arithmetic is unmistakable:

Fig. 2 — the same 10 + 5, read as plain arithmetic, as a sum inside mod 12, and as the remainder operation that produces it.

Fig. 3 — 15 wraps once around a 12-tick clock and lands on 3, which is exactly 15 mod 12.

Definition

$15 = 1 \times 12 + 3 \implies 15 \bmod 12 = 3$

A few more, so the pattern sets in:

More examples

\begin{aligned} 17 \bmod 5 &= 2 \quad (17 = 3 \times 5 + 2) \\ 20 \bmod 7 &= 6 \quad (20 = 2 \times 7 + 6) \\ 12 \bmod 4 &= 0 \quad (12 = 3 \times 4 + 0) \end{aligned}

A result of $0$ just means the division was exact — nothing left over.

Congruence notation

Math has its own shorthand for “these two numbers leave the same remainder”: congruence, written with three bars instead of the usual two.

Congruence

\begin{aligned} 17 &\equiv 2 \pmod{5} \quad (17 \bmod 5 = 2) \\ 22 &\equiv 2 \pmod{5} \quad (22 \bmod 5 = 2) \end{aligned}

Read $17 \equiv 2 \pmod 5$ as ” $17$ is congruent to $2$ , modulo $5$ .” It doesn’t claim $17$ and $2$ are the same number — only that dividing either one by $5$ leaves the same remainder. $22$ lands in that same statement for exactly the same reason: three genuinely different numbers, all behaving identically inside mod $5$ .

The three-bar symbol is doing real work here: two bars ( $=$ ) means identical values; three bars ( $\equiv$ ) means “same remainder, possibly very different numbers.”

Arithmetic inside a modulus

Addition, subtraction, and multiplication all work inside a modulus too — compute normally, then reduce by the modulus. Whatever you started with, the answer always lands back inside $\{0, 1, \ldots, n-1\}$ , which is what makes this a closed system: the operations can never produce a result that escapes the range.

Fig. 4 — every result of addition, subtraction, or multiplication mod 7 lands back on one of these seven points. Nothing escapes the ring.

Addition, mod 7

$5 + 4 = 9, \quad 9 \bmod 7 = 2$

Subtraction, mod 7

$2 - 5 = -3$

Negative numbers aren’t allowed in this range, so add the modulus back on until the result turns positive: $-3 + 7 = 4$ . That’s the actual result — subtraction mod $7$ of $2 - 5$ is $4$ , not $-3$ .

Multiplication, mod 7

$4 \times 5 = 20, \quad 20 \bmod 7 = 6$

Add, subtract, or multiply — the output is always back inside range, every time. That guarantee is the entire point.

Why Circom lives inside this

Every Circom circuit does its arithmetic modulo $p$ , the same enormous prime from the previous lesson. Every signal a circuit touches is a number somewhere in $\{0, 1, \ldots, p-1\}$ , and every addition, subtraction, or multiplication wraps back into that same range, exactly like the examples above just at a far larger scale. This structure — modular arithmetic over a prime — has its own name: a finite field, written $GF(p)$ . That’s the entire reason a circuit’s arithmetic stays predictable instead of spiraling into arbitrarily large numbers, and it’s the subject the next-but-one lesson in this track covers in full. First, though, there’s one more piece modular arithmetic needs: what it means to divide inside a modulus, which is where modular inverses and Fermat’s little theorem come in.