Modular Inverses & Fermat's

The last lesson covered addition, subtraction, and multiplication inside a modulus, and quietly skipped the fourth operation. That gap gets fixed here — division turns out to be the one operation that doesn’t survive the trip into modular arithmetic unchanged, and patching it back in is what this lesson is about.

Why division breaks

In ordinary arithmetic, dividing by a number is identical to multiplying by its reciprocal: $6 \div 2$ and $6 \times \tfrac{1}{2}$ land on the same $3$ . The trouble is that a modulus only has whole numbers to work with — there’s no slot in $\{0, 1, \ldots, n-1\}$ for a fraction like $\tfrac{1}{2}$ to occupy.

Fig. 1 — the same division, rewritten as a reciprocal, breaks the moment it's asked to live inside mod 7.

What stands in for the reciprocal instead is called a modular inverse: a whole number that, multiplied by the original, lands on exactly $1$ .

Modular inverse

$a \times x \equiv 1 \pmod{n}$

$x$ is the modular inverse of $a$ — the number that undoes multiplying by $a$ , the same job a reciprocal does everywhere else.

Finding one by brute force

For small numbers, there’s nothing cleverer to do than try every candidate. Take $3 \bmod 7$ : run $x = 1$ through $x = 5$ and check which one lands on $1$ .

Fig. 2 — checking 3 × x against every x from 1 to 5. x = 5 is the first one that lands on 1.

Verifying the result

$3 \times 5 = 15, \quad 15 \bmod 7 = 1 \implies 3^{-1} \equiv 5 \pmod{7}$

Why not every number has one

Brute force doesn’t always end in success. Try the same search for $2 \bmod 6$ :

Fig. 3 — every x from 1 to 5, checked against 2 × x ≡ 1 (mod 6). None of them land on 1.

No candidate works, and the reason is a single number: the greatest common divisor of $a$ and $n$ .

When an inverse exists

$\gcd(a, n) = 1$

An inverse exists only when $a$ and $n$ share no common factor besides $1$ . $\gcd(2, 6) = 2$ , which is exactly why the search above never found one. It’s also why ZK systems build their modulus out of a prime number: every value from $1$ to $p-1$ automatically shares no factor with a prime $p$ , so every one of them is guaranteed an inverse.

Fermat’s little theorem: a shortcut for huge primes

Brute force works fine for $6 \bmod 7$ , and falls apart completely once the modulus is a 254-bit prime — no computer is checking that many candidates one at a time. Fermat’s little theorem is the shortcut that replaces the search with a single formula.

Fermat's little theorem

$a^{p-1} \equiv 1 \pmod{p}$

Holds whenever $p$ is prime and $a$ isn’t a multiple of $p$ — true for every number from $1$ to $p-1$ , no exceptions.

Three lines turn that statement into a formula for the inverse itself, just by splitting the exponent apart and lining the result up against the definition from the start of this lesson:

Fig. 4 — splitting Fermat's exponent in two turns the theorem directly into the inverse formula.

The inverse formula

$a^{-1} \equiv a^{p-2} \pmod{p}$

Raise $a$ to the power of $p - 2$ , reduce by $p$ , and whatever comes out is the inverse — no search required.

Checking the formula against the brute-force answer

The whole point of a formula is that it has to agree with the slow method it’s replacing. Plug $a = 3$ , $p = 7$ back in:

Worked example

\begin{aligned} 3^{-1} &\equiv 3^{7-2} \pmod{7} \\ &\equiv 3^5 \pmod{7} \\ &\equiv 243 \bmod 7 \\ &\equiv 5 \pmod{7} \end{aligned}

Matches the brute-force answer from a few sections back exactly — $5$ , both times.

Why Circom secretly computes this

There’s no division gate inside a finite field. A Circom circuit can’t compute $a \div b \pmod{p}$ directly, because — same as everywhere else in this lesson — that operation doesn’t exist there. What it computes instead is $a$ times $b$ ‘s modular inverse.

Fig. 5 — every division written in a Circom circuit compiles down to a multiplication by a modular inverse.

Every constraint in a circuit that looks like division is, underneath, running exactly the formula from this lesson. The next lesson gives this whole structure — a modulus, closed under addition, subtraction, multiplication, and now division too — its proper name: a finite field.