Quant Academy Math · Probability · Quant Finance
Phase 19 - Lesson 19.3

Modular Arithmetic, Inverses, and Fast Exponentiation

Working in \(\Z/n\Z\): congruences, inverses, Fermat and Euler, the Chinese Remainder Theorem, and computing \(a^b\bmod n\) in \(O(\log b)\) multiplications.

⏱ 60 min● Intermediate🔗 Prereqs: 19.1 extended Euclid; 19.2 primes and totient
↖ Phase 19 hub
Builds on: 19.1’s Bézout coefficients ARE modular inverses; 19.2 supplied \(\varphi\).
Leads to: 19.13 exponentiates matrices with the same doubling trick; the Euler Lab’s Number Theory path is saturated with ‘give the last 10 digits’ problems that require modpow.

Learning Objectives

Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.

Key Vocabulary

Congruence
\(a\equiv b\pmod n\) iff \(n\mid a-b\); an equivalence relation whose classes are the \(n\) residues.
Unit / invertible residue
\(a\) with \(\gcd(a,n)=1\); exactly these have an inverse mod \(n\), and they form a group \((\Z/n\Z)^\times\) of size \(\varphi(n)\).
Fermat’s little theorem
For prime \(p\) and \(p\nmid a\): \(a^{p-1}\equiv1\pmod p\). Hence \(a^{-1}\equiv a^{p-2}\).
Euler’s theorem
For \(\gcd(a,n)=1\): \(a^{\varphi(n)}\equiv1\pmod n\); so exponents may be reduced mod \(\varphi(n)\).
Binary exponentiation
Square-and-multiply: \(a^b\) from the binary digits of \(b\) using \(\le 2\log_2 b\) modular multiplications.
Chinese Remainder Theorem
For pairwise coprime \(n_1..n_k\), the map \(x\mapsto(x\bmod n_i)\) is a ring isomorphism \(\Z/N\Z\cong\prod\Z/n_i\Z\), \(N=\prod n_i\).

Intuition & Motivation

Intuition
Modular arithmetic is arithmetic on a clock. The two things that break versus the integers are: division (only some residues can be divided by) and comparison (there is no order). Everything else - adding, multiplying, expanding polynomials - works exactly as usual, which is why you can reduce at every step and never let numbers grow. That single discipline turns ‘compute \(2^{1000000}\)’ from impossible into 20 lines and a millisecond.

Congruence is a ring structure

Proposition - Well-definedness
If \(a\equiv a'\) and \(b\equiv b' \pmod n\) then \(a+b\equiv a'+b'\) and \(ab\equiv a'b'\pmod n\).
Proof
Write \(a'=a+kn,\ b'=b+\ell n\). Then \(a'+b'=(a+b)+(k+\ell)n\) and \(a'b'=ab+n(a\ell+bk+k\ell n)\); both differ from the originals by a multiple of \(n\).

Practical consequence: reduce mod \(n\) after every operation. The answer is unchanged and the operands never grow. Python’s big integers hide the cost of forgetting this - but \(2^{10^6}\) is a 300 000-digit number, and multiplying such things is thousands of times slower than staying inside \([0,n)\).

Inverses: exactly the units

Theorem - Existence of \(a^{-1}\bmod n\)
\(a\) has a multiplicative inverse mod \(n\) if and only if \(\gcd(a,n)=1\), and then the inverse is the Bézout coefficient \(x\) in \(ax+ny=1\), reduced into \([0,n)\).
Proof
(\(\Leftarrow\)) Bézout gives \(ax+ny=1\); reduce mod \(n\) to get \(ax\equiv1\). (\(\Rightarrow\)) If \(ax\equiv1\pmod n\) then \(ax-1=kn\), so \(ax-kn=1\) and any common divisor of \(a\) and \(n\) divides 1.
Two roads to an inverse
Extended Euclid works for any modulus and costs \(O(\log n)\). Fermat’s \(a^{-1}\equiv a^{p-2}\pmod p\) works only for prime moduli and costs \(O(\log p)\) multiplications. Use Euclid unless you already have a modpow and the modulus is prime.

Fast exponentiation

Write \(b\) in binary, \(b=\sum_i b_i 2^i\). Then \(a^{b}=\prod_{i:\,b_i=1} a^{2^i}\), and the powers \(a^{2^i}\) are obtained by repeated squaring:

\[a^{b}\bmod n:\quad \text{result}\leftarrow1;\ \ \text{while }b\gt 0:\ \big[\,b\ \text{odd}\Rightarrow \text{result}\leftarrow \text{result}\cdot a\bmod n\,\big],\ a\leftarrow a^2\bmod n,\ b\leftarrow\lfloor b/2\rfloor.\] (19.5)

Each loop iteration halves \(b\), so there are \(\lfloor\log_2 b\rfloor+1\) iterations and at most two modular multiplications per iteration: \(O(\log b)\) total, versus \(b-1\) for the naive loop. For \(b=10^{18}\) that is 60 iterations instead of a quintillion.

Worked Example - Compute \(7^{222}\bmod 11\) two ways
1
Route A (Fermat). 11 is prime and \(11\nmid7\), so \(7^{10}\equiv1\pmod{11}\). Reduce the exponent: \(222=22\cdot10+2\), so \(7^{222}\equiv 7^{2}=49\equiv 5\pmod{11}\).
2
Route B (square-and-multiply, no shortcuts). \(222=11011110_2\). Squarings: \(7^1=7,\ 7^2=49\equiv5,\ 7^4\equiv5^2=25\equiv3,\ 7^8\equiv3^2=9,\ 7^{16}\equiv81\equiv4,\ 7^{32}\equiv16\equiv5,\ 7^{64}\equiv25\equiv3,\ 7^{128}\equiv9\).
3
The bits of 222 are \(128+64+16+8+4+2\). Multiply those powers: \(9\cdot3=27\equiv5\); \(5\cdot4=20\equiv9\); \(9\cdot9=81\equiv4\); \(4\cdot3=12\equiv1\); \(1\cdot5=5\).
4
Both routes give \(\boxed{5}\). Route A used one exponent reduction; route B used 7 squarings and 5 multiplications - and route B is the one that generalises to composite moduli.
5
Warning: exponent reduction by \(\varphi(n)\) requires \(\gcd(a,n)=1\). \(2^{222}\bmod 10\) cannot be done by reducing 222 mod \(\varphi(10)=4\) naively, because \(\gcd(2,10)=2\).

The Chinese Remainder Theorem

Theorem - CRT
Let \(n_1,\dots,n_k\) be pairwise coprime, \(N=\prod n_i\). For any residues \(r_i\) there is a unique \(x\in[0,N)\) with \(x\equiv r_i\pmod{n_i}\) for all \(i\).
Proof
Uniqueness: if \(x,x'\) both work then \(n_i\mid x-x'\) for all \(i\), and pairwise coprimality gives \(N\mid x-x'\), so \(x=x'\) in \([0,N)\). Existence: set \(M_i=N/n_i\); since \(\gcd(M_i,n_i)=1\) there is \(M_i^{-1}\bmod n_i\) (19.1). Then \(x=\sum_i r_i M_i (M_i^{-1}\bmod n_i)\bmod N\) satisfies each congruence, because every term but the \(i\)-th vanishes mod \(n_i\).
Key Idea
CRT is a divide-and-conquer for arithmetic: a hard computation mod a big \(N\) splits into independent easy computations mod each prime power, then reassembles. It is also how you dodge overflow in fixed-width languages, and how you count solutions of \(f(x)\equiv0\pmod N\) by multiplying counts.

Coding workbench

In the Euler Lab, modular arithmetic is the difference between an answer and an overflow: problems that ask for the last digits of a gigantic quantity are asking you to never build the gigantic quantity. That is the whole lesson.

Common Mistakes to Avoid
  • Reducing an exponent mod \(n\) instead of mod \(\varphi(n)\) - exponents live in a different world from bases.
  • Applying Euler’s theorem when \(\gcd(a,n)\ne1\). It is simply false there (use lifting-the-exponent or CRT on prime powers instead).
  • Forgetting that Python’s % of a negative number is already non-negative, then ‘fixing’ it and introducing a bug - or porting to C and forgetting to fix it there.
  • Dividing by \(k\) in a modular formula (e.g. a binomial coefficient) instead of multiplying by \(k^{-1}\). Modular division does not exist; modular multiplication by an inverse does.
  • Using CRT with non-coprime moduli. Then the system may be inconsistent, or have \(\gcd\) solutions - you need the generalized CRT with a solvability check.
Quant Practitioner Tips
  • Prime moduli like \(10^9+7\) are chosen so that every nonzero residue is invertible - that is why competitive problems ask for answers mod a prime.
  • Precompute factorials and inverse factorials mod \(p\) once; then any binomial \(\binom{n}{k}\bmod p\) is an \(O(1)\) lookup (19.5).
  • Python’s pow(a,b,n) is a C implementation of exactly (19.5), and pow(a,-1,n) gives the inverse. Write your own once to understand it, then use the built-in.

Practice this in the Euler Lab

Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.

Warm-up:
#1 Multiples of 3 or 5 (1%, tier A) #2 Even Fibonacci Numbers (1%, tier A) #7 10 001st Prime (1%, tier A) #20 Factorial Digit Sum (1%, tier A)

Applied:
#293 Pseudo-Fortunate Numbers (16%, tier B) #313 Sliding Game (16%, tier B) #357 Prime Generating Integers (16%, tier B)

Challenge:
#161 Triominoes (41%, tier C) #182 RSA Encryption (41%, tier C)

483 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.

Knowledge Check

Q1 Easy
When does \(a\) have an inverse modulo \(n\)?
Whenever \(a\lt n\)
Whenever \(n\) is prime
Exactly when \(\gcd(a,n)=1\)
Whenever \(a\) is prime
Q2 Medium
How many modular multiplications does square-and-multiply need for \(a^{10^{18}}\bmod n\)?
About \(10^{18}\)
About 120 - two per bit of the exponent
About \(\sqrt{10^{18}}=10^9\)
It depends on \(a\)
Q3 Medium
You want \(x\equiv2\pmod 3\) and \(x\equiv3\pmod 5\). CRT gives:
\(x\equiv5\pmod{15}\)
\(x\equiv8\pmod{15}\)
\(x\equiv13\pmod{15}\)
No solution

Practical Exercise

(a) Compute the last three digits of \(7^{1234567}\) by hand, i.e. \(7^{1234567}\bmod1000\), using Euler’s theorem and CRT. (b) Explain precisely why you may reduce the exponent mod \(\varphi(1000)\) here, and give an \(a\) for which you may not.

▶ Show full solution

(a) \(1000=8\cdot125\), which are coprime, so work mod 8 and mod 125 and glue with CRT.

Mod 8: \(7\equiv-1\), so \(7^{1234567}\equiv(-1)^{\text{odd}}=-1\equiv7\pmod 8\).

Mod 125: \(\varphi(125)=100\) and \(\gcd(7,125)=1\), so exponents reduce mod 100: \(1234567\equiv67\pmod{100}\), giving \(7^{67}\bmod125\). By square-and-multiply: \(7^2=49\), \(7^4=49^2=2401\equiv26\), \(7^8\equiv26^2=676\equiv51\), \(7^{16}\equiv51^2=2601\equiv101\), \(7^{32}\equiv101^2=10201\equiv76\), \(7^{64}\equiv76^2=5776\equiv26\). Now \(67=64+2+1\): \(7^{67}\equiv26\cdot49\cdot7\). \(26\cdot49=1274\equiv1274-1250=24\); \(24\cdot7=168\equiv43\pmod{125}\).

CRT: find \(x\equiv7\pmod 8,\ x\equiv43\pmod{125}\). Write \(x=43+125t\); then \(43+125t\equiv7\pmod 8\). Since \(43\equiv3\) and \(125\equiv5\pmod 8\): \(3+5t\equiv7\Rightarrow5t\equiv4\pmod8\). \(5^{-1}\equiv5\pmod8\) (as \(25\equiv1\)), so \(t\equiv20\equiv4\pmod8\). Thus \(x=43+125\cdot4=543\).

Answer: the last three digits are 543. (Verify: pow(7,1234567,1000) returns 543.)

(b) Euler’s theorem \(a^{\varphi(n)}\equiv1\) requires \(\gcd(a,n)=1\), which holds for \(a=7,\ n=125\) (and mod 8). For \(a=10\) and \(n=1000\) it fails: \(\gcd(10,1000)=10\), and indeed \(10^k\bmod1000\) is eventually always 0, never returning to 1. There you split \(1000=8\cdot125\) and handle the non-coprime prime power directly (the powers of 2 in \(a\) simply saturate).

After the reveal, answer for yourself: Notice that CRT let you replace one hard exponentiation mod 1000 by two easy ones. When is the split worth the extra bookkeeping?

Lesson Summary

Congruences make \(\Z/n\Z\) a ring in which you may reduce after every operation - the discipline that keeps numbers small. Inverses exist exactly for units \((\gcd(a,n)=1)\) and come from extended Euclid; Fermat and Euler let you reduce exponents mod \(p-1\) or \(\varphi(n)\) (only when the base is coprime to the modulus). Square-and-multiply computes \(a^b\bmod n\) in \(O(\log b)\) multiplications, and CRT splits a computation mod \(N\) into independent pieces mod each prime power.

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers
Q: Give the two ways to compute \(a^{-1}\bmod n\) and their preconditions.
A: Extended Euclid: works for any \(n\) with \(\gcd(a,n)=1\), cost \(O(\log n)\). Fermat: \(a^{p-2}\bmod p\), requires a PRIME modulus, cost \(O(\log p)\) multiplications.
Q: Why is square-and-multiply \(O(\log b)\)?
A: Each iteration halves \(b\) (one squaring), and multiplies into the accumulator only on a 1-bit. So the number of iterations is the bit-length of \(b\), with ≤2 modular multiplications each.

Completion Checklist

Confidence / mastery rating
Personal notes

Source References

This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.

← 19.2Next: 19.4 →