Computational number theory is often the art of refusing to compute an enormous integer when only a small residue is needed.
Expressions such as a^e mod n appear innocent until the exponent e becomes large. Expanding a^e first and reducing afterward is usually the wrong computational model. The better idea is to reduce after every multiplication and to exploit the binary structure of the exponent. The resulting square-and-multiply method turns an exponent requiring e−1 multiplications into a calculation requiring only on the order of log₂e squarings and multiplications.
The same philosophy appears in the Chinese Remainder Theorem. Instead of solving one large modular problem directly, we may work in several smaller modular systems and then reconstruct the unique solution. This guide develops both ideas as algorithms, not merely formulas.
This is Guide 2 in the Bukit Timah Tutor Computational Number Theory series. Return to the BTT Mathematics Hub for the wider Mathematics route.
Compress the exponent. Reduce the residues. Recombine only what must be recombined.
1. Why direct exponentiation is the wrong starting point
Suppose we want 7^222 mod 1000. The integer 7^222 has 188 decimal digits. None of those digits, except the information determining the remainder modulo 1000, is needed for the final answer.
Modular arithmetic lets us discard irrelevant information continuously. If x≡y (mod n), then xz≡yz (mod n). So after every multiplication we may replace the intermediate value by its remainder modulo n.
This protects two things at once: correctness and size. The residue remains mathematically equivalent for the task, while the stored numbers stay bounded by the modulus.
2. Repeated squaring
Every positive exponent has a binary expansion. For example,
222 = 128 + 64 + 16 + 8 + 4 + 2
= 11011110₂.
Therefore
7^222 = 7^128 · 7^64 · 7^16 · 7^8 · 7^4 · 7^2.
We can obtain each power of two by squaring the previous residue:
7^1 ≡ 7 (mod 1000) 7^2 ≡ 49 (mod 1000) 7^4 ≡ 401 (mod 1000) 7^8 ≡ 801 (mod 1000) 7^16 ≡ 601 (mod 1000) 7^32 ≡ 201 (mod 1000) 7^64 ≡ 401 (mod 1000) 7^128 ≡ 801 (mod 1000)
Multiplying only the residues corresponding to 1-bits in 222 and reducing at each step gives
7^222 ≡ 49 (mod 1000).
The important result is not the particular remainder 49. It is the transformation of the exponent into a logarithmic-length sequence of controlled operations.
3. Binary modular exponentiation
A standard right-to-left algorithm is:
mod_pow(base, exponent, modulus):
result = 1
base = base mod modulus
while exponent > 0:
if exponent is odd:
result = (result · base) mod modulus
base = (base · base) mod modulus
exponent = floor(exponent / 2)
return result
At each loop, one binary digit of the exponent is consumed. If the exponent has k bits, the loop runs k times. That is why the number of modular multiplications grows with log₂e rather than e.
4. The invariant behind square-and-multiply
An algorithm is easier to trust when we can state what remains true during execution. In the right-to-left method, suppose the original problem is a^e mod n. During the loop we maintain values result, base and exponent such that
result · base^exponent ≡ a^e (mod n).
If exponent is odd, write exponent=2q+1. Moving one factor of base into result and replacing base by base² leaves the represented product unchanged. If exponent is even, exponent=2q, and base^2q=(base²)^q. The invariant survives both branches.
When exponent reaches zero, base^0=1, so result itself is congruent to the target power. This is a compact correctness proof for the algorithm.
5. Worked example: 5^117 mod 19
Binary decomposition gives 117=64+32+16+4+1. Repeated squaring modulo 19:
5^1 ≡ 5 5^2 ≡ 6 5^4 ≡ 17 5^8 ≡ 4 5^16 ≡ 16 5^32 ≡ 9 5^64 ≡ 5 (mod 19)
Then
5^117 ≡ 5^64 · 5^32 · 5^16 · 5^4 · 5
≡ 5·9·16·17·5
≡ 1 (mod 19).
There is also a theorem-based shortcut here: because 19 is prime and 5 is not divisible by 19, Fermat’s little theorem gives 5^18≡1. Since 117=6·18+9, we may reduce to 5^9 mod 19. The algorithmic method remains essential because it works even when no convenient exponent theorem is available.
6. Fermat’s little theorem as exponent reduction
If p is prime and p∤a, then
a^(p−1) ≡ 1 (mod p).
Therefore exponents may be reduced modulo p−1 when the base is coprime to p. For example, to compute 2^1000 mod 17, use 2^16≡1. Since 1000≡8 (mod 16),
2^1000 ≡ 2^8 ≡ 256 ≡ 1 (mod 17).
The coprimality condition matters. It is unsafe to reduce exponents mechanically without checking the theorem’s hypotheses.
7. Euler’s theorem and the totient function
Euler’s theorem extends the idea from prime moduli to arbitrary positive moduli. Let φ(n) be the number of residues 1≤k≤n that are coprime to n. If gcd(a,n)=1, then
a^φ(n) ≡ 1 (mod n).
For a prime p, φ(p)=p−1, so Fermat’s theorem is the prime case.
If the prime factorisation n=∏p_i^{e_i} is known, then
φ(n)=n∏(1−1/p_i).
Example: n=40=2³·5, so φ(40)=40(1−1/2)(1−1/5)=16. For any a coprime to 40, a^16≡1 (mod 40).
Euler reduction and binary exponentiation complement each other. The theorem may shrink the exponent first; square-and-multiply then evaluates the remaining power efficiently.
8. Carmichael’s function: a tighter universal exponent
Euler’s φ(n) is not always the smallest exponent that works for every unit modulo n. The Carmichael function λ(n) is the exponent of the multiplicative group modulo n: for every a coprime to n,
a^λ(n) ≡ 1 (mod n).
Because λ(n) divides φ(n), it can offer a stronger reduction. For example, φ(15)=8, but λ(15)=4. Every residue coprime to 15 satisfies a^4≡1 (mod 15).
This distinction becomes useful in more advanced modular algorithms, but the same caution remains: these exponent reductions apply only to units, meaning residues coprime to the modulus.
9. Modular powers when the base is not coprime to the modulus
If gcd(a,n)≠1, Euler’s theorem cannot simply be invoked. That does not make the modular power difficult; binary exponentiation still works without any coprimality condition.
Example: compute 6^20 mod 15. Since 6²=36≡6 (mod 15), every positive power of 6 is congruent to 6. The answer is 6. Euler reduction would be invalid because gcd(6,15)=3.
This illustrates a useful hierarchy:
- Binary modular exponentiation is the general-purpose algorithm.
- Fermat, Euler or Carmichael may reduce work when their hypotheses hold.
- Special algebraic patterns may simplify the residue even further.
10. From one modulus to many
Suppose an integer x must satisfy several congruences:
x ≡ a₁ (mod n₁) x ≡ a₂ (mod n₂) ... x ≡ a_k (mod n_k).
If the moduli are pairwise coprime, the Chinese Remainder Theorem says there is exactly one solution modulo N=n₁n₂…n_k.
The theorem performs a remarkable change of representation. One residue modulo a large product N can be represented by a tuple of smaller residues. Arithmetic can be done componentwise and then reconstructed.
11. Why uniqueness is modulo the product
Suppose x and y satisfy the same system with pairwise coprime moduli. Then each n_i divides x−y. Because the n_i are pairwise coprime, their product N also divides x−y. Hence x≡y (mod N).
So the theorem does not claim one unique integer. It claims one unique residue class modulo N.
12. Constructive CRT formula
Let N=n₁n₂…n_k and define N_i=N/n_i. Because n_i is coprime to every other modulus, gcd(N_i,n_i)=1. Therefore N_i has an inverse modulo n_i. Call that inverse M_i:
N_i M_i ≡ 1 (mod n_i).
Then
x ≡ Σ a_i N_i M_i (mod N).
Why does this work? For a fixed j, every term with i≠j contains n_j as a factor through N_i, so those terms vanish modulo n_j. The j-th term becomes a_j·1. The construction isolates each residue and then adds the isolated components together.
13. Worked CRT example
Solve
x ≡ 2 (mod 3) x ≡ 3 (mod 5) x ≡ 2 (mod 7).
The moduli are pairwise coprime and N=3·5·7=105.
- For n₁=3: N₁=35, and 35≡2 mod 3. The inverse of 2 mod 3 is 2, so M₁=2.
- For n₂=5: N₂=21, and 21≡1 mod 5. Thus M₂=1.
- For n₃=7: N₃=15, and 15≡1 mod 7. Thus M₃=1.
Construct
x ≡ 2·35·2 + 3·21·1 + 2·15·1 ≡ 140 + 63 + 30 ≡ 233 ≡ 23 (mod 105).
Check: 23 mod 3=2, 23 mod 5=3, and 23 mod 7=2.
14. Incremental CRT
The closed formula is elegant, but an incremental construction is often easier by hand and can be convenient in software. Combine two congruences first, then combine the result with the next.
For the same system, begin with x≡2 (mod 3), so x=2+3t. Impose x≡3 (mod 5):
2 + 3t ≡ 3 (mod 5) 3t ≡ 1 (mod 5) t ≡ 2 (mod 5).
Thus x=2+3(2+5s)=8+15s, so x≡8 (mod 15). Now impose x≡2 (mod 7):
8 + 15s ≡ 2 (mod 7) 1 + s ≡ 2 (mod 7) s ≡ 1 (mod 7).
Hence x=8+15(1+7u)=23+105u.
15. Generalised CRT when moduli are not coprime
The pairwise-coprime version is the cleanest theorem, but systems with overlapping moduli can still have solutions.
For
x ≡ a (mod m) x ≡ b (mod n),
a solution exists if and only if
a ≡ b (mod gcd(m,n)).
If it exists, the solution is unique modulo lcm(m,n).
Example: x≡2 mod 6 and x≡5 mod 9
gcd(6,9)=3, and 2≡5 (mod 3), so the system is compatible. Testing the class x=2+6t modulo 9 gives 6t≡3 (mod 9), which reduces to 2t≡1 (mod 3), so t≡2 (mod 3). Thus x=14+18u.
The solution is therefore x≡14 (mod 18), and 18=lcm(6,9).
16. CRT as a representation system
For pairwise coprime moduli n₁,…,n_k, the map
x mod N ↦ (x mod n₁, …, x mod n_k)
is a one-to-one correspondence between residues modulo N and residue tuples. Addition and multiplication happen componentwise:
(a₁,…,a_k) + (b₁,…,b_k) = (a₁+b₁,…,a_k+b_k) (a₁,…,a_k) · (b₁,…,b_k) = (a₁b₁,…,a_kb_k),
with each component reduced in its own modulus. This can make a large modular computation decomposable into smaller independent pieces.
17. Modular exponentiation through CRT
Suppose n=pq with distinct primes p and q, and we want a^e mod n. We may compute
r_p = a^e mod p r_q = a^e mod q
using fast exponentiation, then reconstruct the unique residue modulo pq via CRT. The decomposition can reduce arithmetic cost and also makes local verification easier: each component can be checked independently.
The general lesson is not tied to one application. When a ring modulo a composite integer decomposes into simpler coprime components, computation may be moved into those components and returned afterward.
18. Overflow and implementation discipline
Mathematical pseudocode assumes exact integers. Real programming languages may use fixed-width machine integers. Even if x and y are each less than n, the product xy may overflow before the remainder is taken.
Possible remedies include arbitrary-precision integer types, wider intermediate types, or specialised modular multiplication algorithms. The correct choice depends on the language, modulus size and performance requirements.
This is an important computational distinction: the formula (xy) mod n is mathematically harmless, but an implementation must ensure the intermediate multiplication represents xy correctly.
19. Negative exponents modulo n
A negative modular exponent a^(−k) makes sense only when a has an inverse modulo n. If gcd(a,n)=1, first compute a⁻¹ using the extended Euclidean algorithm, then evaluate (a⁻¹)^k using modular exponentiation.
Example: 3^(−2) mod 11. The inverse of 3 modulo 11 is 4, so 3^(−2)≡4²≡16≡5 (mod 11).
If gcd(a,n)≠1, no multiplicative inverse exists, so a negative exponent is not defined in the unit group modulo n.
20. Common mistakes
- Expanding first: computing a^e as a huge integer before reducing wastes information and may be impossible.
- Forgetting to reduce intermediates: residues should be controlled after every multiplication.
- Reducing exponents without hypotheses: Fermat, Euler and Carmichael reductions require coprimality conditions.
- Assuming CRT always applies in its simple form: pairwise coprimality must be checked, or the general compatibility condition must be used.
- Claiming a unique integer: CRT gives a unique residue class modulo the product or lcm.
- Using an inverse that does not exist: every CRT inverse N_i⁻¹ mod n_i depends on gcd(N_i,n_i)=1.
- Ignoring machine overflow: correct modular Mathematics can still be implemented incorrectly.
21. Practice set
- Compute 3^200 mod 50 using repeated squaring or a valid theorem.
- Compute 11^73 mod 17.
- Write 345 in binary decomposition form as a sum of powers of two.
- Explain why binary exponentiation uses O(log e) loop iterations.
- Compute 7^128 mod 13.
- Solve x≡1 (mod 4), x≡2 (mod 5), x≡3 (mod 7).
- Solve x≡4 (mod 9), x≡1 (mod 5).
- Determine whether x≡1 (mod 6), x≡2 (mod 9) is solvable.
- Determine whether x≡4 (mod 6), x≡1 (mod 9) is solvable.
- Compute 5^(−1) mod 12.
- Compute 5^(−3) mod 12.
- Explain why CRT reconstruction can be viewed as building selector residues.
22. Answers and checks
1. Since gcd(3,50)=1 and φ(50)=20, 3^200=(3^20)^10≡1. Direct repeated squaring agrees.
2. By Fermat, 11^16≡1 (mod 17). Since 73≡9 (mod 16), compute 11^9≡6 (mod 17).
3. 345=256+64+16+8+1=2^8+2^6+2^4+2^3+2^0.
4. Each iteration halves the remaining exponent. After k halvings, e/2^k<1 when k is about log₂e.
5. Fermat gives 7^12≡1 mod 13. Since 128≡8 mod 12, 7^128≡7^8≡3 mod 13.
6. The solution is x≡17 (mod 140). Check: 17 mod 4=1, mod 5=2, mod 7=3.
7. x≡31 (mod 45).
8. gcd(6,9)=3, but 1 is not congruent to 2 modulo 3. No solution.
9. 4≡1 (mod 3), so the system is compatible. One solution is x≡10 (mod 18).
10. 5·5=25≡1 (mod 12), so 5⁻¹≡5.
11. Since 5⁻¹≡5 and 5²≡1, 5^(−3)≡5³≡5 (mod 12).
12. Each term N_iM_i is congruent to 1 in its own modulus and 0 in every other modulus, so it selects one coordinate without disturbing the rest.
23. The computational pattern
Fast modular exponentiation and CRT look like different topics, but they teach the same deeper habit: preserve only the information the problem requires.
- Large powers become short binary instruction sequences.
- Intermediate integers become bounded residues.
- One composite modulus can become several smaller coprime moduli.
- Reconstruction happens only after the simpler local computations are complete.
- Correctness is protected by explicit invariants and verification.
The next guide asks a different computational question: given an integer n, how can an algorithm decide whether n is prime without first finding a factor?
24. Continue the series
- Guide 1: Euclidean Algorithm, Bézout Identity and Modular Inverses
- Guide 2: Fast Modular Exponentiation and the Chinese Remainder Theorem
- Guide 3: Prime Sieves and Primality Testing
- Guide 4: Integer Factorisation and Computational Limits
Return to the Singapore Mathematics Hub for the wider BTT Mathematics library.