Modular Arithmetic
At 10 o'clock, what time will it be in 5 hours? Not 15 — it will be 3. A clock forgets everything except the remainder after dividing by 12. Modular arithmetic is arithmetic that forgets in exactly that way, on purpose: we keep only the remainder after division by a fixed number , called the modulus.
That sounds like a toy, and it is the opposite. It is how every problem that says "print the answer modulo " keeps a number with 50,000 digits inside one machine word. It is how hash functions mix bits, how random-number generators step, how ISBN and IBAN check digits catch typos, how RSA encrypts your bank session, and how the number-theoretic transform multiplies polynomials with no rounding errors. Underneath all of them is one fact: you can add, subtract and multiply remainders, and get the remainder of the true result. Division is the one operation that needs care — and handling it is most of this lesson.
You need Number Theory I (GCD, extended Euclid, Bézout's identity, factorization, the sieve). Everything here is built on those.
Why this exists
Three pressures created modular arithmetic as a programming tool.
- Numbers too big to store. "How many ways to tile a board?" has a 209-digit answer. Problem setters ask for it modulo a prime so that answers fit in 64 bits and can be checked; you need arithmetic that never builds the huge number. The same pressure appears in Counting DP, Matrix Exponentiation and String Hashing.
- Wrap-around is how hardware works. A 32-bit unsigned integer is arithmetic modulo :
0xFFFFFFFF + 1 == 0. Hash functions, checksums and pseudo-random generators exploit this deliberately. - Cryptography. In 1977 Rivest, Shamir and Adleman published RSA, whose security rests on the claim that computing is easy while undoing it is hard without knowing the factors of . Diffie–Hellman (1976) and elliptic-curve cryptography are also modular arithmetic. Every TLS handshake runs thousands of modular multiplications.
The mathematics is old. Carl Friedrich Gauss introduced the notation in Disquisitiones Arithmeticae (1801). Fermat stated his "little theorem" in a 1640 letter; Euler proved it and generalised it in the 1700s. The Chinese Remainder Theorem appears as a puzzle in the Sunzi Suanjing, a Chinese text from roughly the 3rd to 5th century AD: "There are things whose number is unknown. Counted by threes, two remain; by fives, three remain; by sevens, two remain. How many things?" (We solve it below: 23.)
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "return the answer modulo " | Reduce after every +, -, *; never divide directly |
| with up to | Fast (binary) exponentiation, |
| "divide" under a modulus, | Multiply by the modular inverse |
| Inverse modulo a prime | Fermat: |
| Inverse modulo a composite | Extended Euclid; exists only if |
| for many queries, | Precomputed factorials and inverse factorials |
| Exponent itself huge (, exponent given as a string) | Reduce the exponent modulo (Fermat) or (Euler) |
| "count integers in coprime to " | Euler's totient |
| ", , …" | Chinese Remainder Theorem |
| "cycles of lengths , — when do they line up at given offsets?" | CRT with non-coprime moduli |
| Product of two numbers near modulo | Safe mulmod: 128-bit product, or Montgomery/Barrett |
| Polynomial multiplication with exact integer coefficients | NTT modulo 998244353 (FFT & NTT) |
| Hash a string, compare substrings | Polynomial hash modulo a large prime (String Hashing) |
Intuition & first principles
Congruence
Fix a modulus . Two integers and are congruent modulo , written
when divides . Equivalently, and leave the same remainder when divided by . On a 12-hour clock, , and (one hour before midnight is 11).
Congruence splits all integers into classes, called residue classes: for , the classes are , and . We name each class by its smallest non-negative member, . Working "modulo " means working with these names. The set is written (or ).
The three safe operations
If and , then
Why (for multiplication, the interesting one). Write and . Then , which differs from by a multiple of .
In code this means: reduce as early and as often as you like. (a * b) % m == ((a % m) * (b % m)) % m. A long sum or product never has to exist in full. For example, the last digit of is the last digit of a 188-digit number, but modulo 10 you only ever hold one digit (the answer is 9; we compute it below with Euler's theorem).
A worked check: . Directly: . Reducing first: , , , . Same answer, smaller numbers.
Division is the odd one out
Division does not survive reduction. . But and , and is not even an integer. The fix is to stop thinking of division as "" and think of it as "multiply by the number that undoes multiplication by 4". Modulo 7, , so multiplying by 2 undoes multiplying by 4: is the modular inverse of 4 modulo 7, written . Then
An inverse of modulo is any with . It exists exactly when . If , then is never a multiple of , because divides both and but not 1. Example: 2 has no inverse modulo 4 ( is always 0 or 2 mod 4). If , Bézout gives , and reading that modulo gives . That is the extended-Euclid method below.
When is prime, every not divisible by is coprime to , so every non-zero residue has an inverse. That is why contest problems use prime moduli: with a prime, you can add, subtract, multiply and divide (by anything non-zero). Mathematicians call a field.
% and negative numbers: four languages, two answers
What is ? Mathematically, the residue in is (because ). But languages disagree about the % operator:
| Expression | Python | Java | C++ (C++11 and later) | JavaScript / TypeScript |
|---|---|---|---|---|
7 % 3 | 1 | 1 | 1 | 1 |
-7 % 3 | 2 | −1 | −1 | −1 |
7 % -3 | −2 | 1 | 1 | 1 |
| Rule | result has the sign of the divisor (floored division) | sign of the dividend (truncated division) | sign of the dividend (truncated) | sign of the dividend (truncated) |
| "Always non-negative" helper | a % m already is (for ) | Math.floorMod(a, m) | ((a % m) + m) % m | ((a % m) + m) % m |
C++ and Java define integer division to round toward zero, so -7 / 3 == -2 and the remainder must be -7 - (-2)(3) = -1. Python rounds toward minus infinity, so -7 // 3 == -3 and the remainder is -7 - (-3)(3) = 2. (In C++ before C++11 the sign was implementation-defined.) JavaScript's % works on doubles and truncates like C. Python's math.fmod(-7, 3) gives -1.0, C-style.
The trap this sets: in C++, Java and JavaScript, (a - b) % m is negative whenever , and a negative "residue" used as an array index or compared with 0 is a bug. Always write ((a - b) % m + m) % m, or (a - b + m) % m when both are already in .
Fermat's little theorem and Euler's theorem
Fermat's little theorem. If is prime and , then
Example: .
Proof sketch. Multiply each of the non-zero residues by . The products are again non-zero and pairwise different modulo (if , multiply by to get ). So they are the same numbers in some order. Multiply all of them: , and is invertible, so .
Euler's totient. For , (Greek "phi") counts the integers in coprime to . , for a prime, (1, 2, 4, 5, 7, 8), . The first twelve values are 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4.
Euler's theorem. If , then
The proof is Fermat's, run over the residues coprime to instead of all non-zero ones. Fermat is the special case .
Computing from the factorization. For a prime power, the numbers in not coprime to are the multiples of , and there are of them, so . And is multiplicative: when (this follows from CRT, below). Together:
. , with : . In code you never use fractions: for each prime of , do result -= result / p, which is exact because divides result at that moment.
Exponent reduction. Euler's theorem lets you shrink huge exponents. If , then . The last digit of : , , , so the last digit is 9. For a prime modulus and : — note , not , a classic bug.
When and are not coprime there is still a rule (sometimes called the generalised Euler theorem): for ,
It is what you need for towers like when might share factors with . (Both forms are tested against brute force in the implementation below.)
The Chinese Remainder Theorem
Theorem. If are pairwise coprime and , then for any remainders the system
has exactly one solution in .
Intuition: knowing a number's remainders modulo 3, 5 and 7 is the same information as knowing its remainder modulo 105. The map sends the 105 residues to the possible triples, and no two residues share a triple (if and do, then 3, 5 and 7 all divide , so 105 does). A one-to-one map between two sets of the same size hits everything. That is the whole existence-and-uniqueness proof. The constructive part — actually finding — is extended Euclid, shown in the mechanics.
Mechanics
1. Fast exponentiation (binary exponentiation)
Computing by multiplying into a result times costs multiplications: of them for a typical contest exponent. Binary exponentiation (also called square-and-multiply) costs .
Idea. Write in binary. , so . The powers come from repeated squaring, each one multiplication. Walk the bits of from the lowest: square the base every step, and multiply it into the result when the current bit is 1.
def power(a, b, m):
result = 1 % m # handles m == 1
a %= m
while b > 0:
if b & 1:
result = result * a % m
a = a * a % m
b >>= 1
return result
Trace: , :
| Step | Bit of (low → high) | result before | Multiply? | result after | base used | base after squaring |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | yes: | 3 | () | |
| 2 | 0 | 3 | no | 3 | () | |
| 3 | 1 | 3 | yes: | 5 | () | |
| 4 | 1 | 5 | yes: | 3 | — |
So . Check with Fermat: , so . Four loop iterations instead of 12 multiplications; for it is 60 iterations instead of .
flowchart TD
S["result = 1, base = a mod m"] --> C{"b > 0?"}
C -->|"no"| R["return result"]
C -->|"yes"| B{"lowest bit of b is 1?"}
B -->|"yes"| M["result = result · base mod m"]
B -->|"no"| Q["base = base · base mod m"]
M --> Q
Q --> H["b = b >> 1"]
H --> C
The same loop works for anything you can multiply associatively: matrices (Matrix Exponentiation computes Fibonacci numbers in this way), permutations, polynomials modulo another polynomial, elements of an elliptic-curve group (there "multiplication" is point addition and the loop is called double-and-add). Python's built-in pow(a, b, m) does it for you; since Python 3.8, pow(a, -1, m) also returns a modular inverse.
2. Modular inverse, three ways
(a) Fermat, for prime . From : , so
One fast exponentiation, . Example: , and indeed .
Fermat only works for prime moduli
For a composite modulus the formula silently returns garbage. Inverse of 3 modulo 8 "by Fermat" would be — but . The true inverse is 3 (). With Euler's theorem the correct general formula is , which needs — usually extended Euclid is simpler.
(b) Extended Euclid, for any modulus with . Find with ; then is the inverse. Also , no primality needed, and it tells you when no inverse exists (the GCD comes out larger than 1).
Trace: (the RSA example below). We only need the coefficient of 17, so track one column with :
| — | 3120 | 17 | 0 | 1 |
| 183 | 17 | 9 | 1 | −183 |
| 1 | 9 | 8 | −183 | 184 |
| 1 | 8 | 1 | 184 | −367 |
| 8 | 1 | 0 | −367 | 3120 |
The last non-zero remainder is 1 (so the inverse exists) with . Make it non-negative: . Check: . ✓
(c) All inverses at once, modulo a prime , in . Write with , . Modulo this says . Multiply both sides by (both exist, since ): , hence
Since , its inverse is already in the table. For the table for is 1, 6, 4, 3, 9, 2, 8, 7, 5, 10.
| Method | Modulus | Cost | Fails how |
|---|---|---|---|
| Fermat | prime only | Silently wrong on composites; returns 0 for | |
| Extended Euclid | any, | Detects and reports "no inverse" | |
| Linear table | prime | for all | Needs |
| Batch trick (prefix products, one inverse) | any, all coprime | for arbitrary values | One non-invertible value breaks it |
3. Euler's totient: one number and a sieve
One number: trial division (from Number Theory I), and for each prime factor apply result -= result / p. .
| Step | Prime found | result before | result -= result / p |
|---|---|---|---|
| start | 36 | ||
| 1 | 2 (36 → 9) | 36 | |
| 2 | 3 (9 → 1) | 18 |
: the numbers 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35.
A totient sieve
For all at once, start with phi[i] = i, and for each prime (detected because phi[p] is still ) apply phi[k] -= phi[k] / p to every multiple of . Like Eratosthenes, it is . The linear sieve from Number Theory I also computes it in with the rule: if divides , then ; otherwise .
4. The Chinese Remainder Theorem, constructively
Two coprime moduli. Solve , with . Every solution of the first equation is . Substitute into the second: , so . Then , unique modulo .
Sunzi's puzzle: , , . Merge two at a time:
| Merge | Current | New equation | Solve for | Result |
|---|---|---|---|---|
| 1 | , | |||
| 2 | (, ) | , |
Check: . ✓ The answer is 23 things (or ).
flowchart LR
A["x ≡ 2 mod 3"] --> M1["merge"]
B["x ≡ 3 mod 5"] --> M1
M1 --> AB["x ≡ 8 mod 15"]
AB --> M2["merge"]
C["x ≡ 2 mod 7"] --> M2
M2 --> R["x ≡ 23 mod 105"]
Non-coprime moduli (the general case). Let . Then forces , and the second equation forces . So a solution exists iff . When it does, the solution is unique modulo (not ). Construction: ; divide everything by : , and now is coprime to , so it has an inverse. Extended Euclid on gives , and is exactly that inverse.
- , : , is even, so solvable. , , ; , unique modulo .
- , : , is odd, so no solution (the first says is odd, the second says even).
For equations, fold: merge the first two into one equation modulo their LCM, merge that with the third, and so on. Keep the running modulus in a 64-bit (or 128-bit, or big) integer and stop with "no solution" at the first inconsistency.
Garner's algorithm is a different way to reconstruct from residues modulo pairwise coprime : it writes in a mixed-radix form with each found using only arithmetic modulo . Its advantage is that it never needs numbers as big as until the very end — or never, if you only want some other modulus. It is the standard way to combine the results of three NTTs modulo three different primes into one exact answer (see FFT & NTT), and big-integer libraries use it in residue-number-system arithmetic.
5. Why and ?
became the default contest modulus because it is:
- Prime, so every non-zero value has an inverse and Fermat works.
- Below , so one residue fits in a signed 32-bit
int, and the sum of two residues () still fits below . - Small enough that a product of two residues fits in a signed 64-bit integer: . So
a * b % MODwith 64-bitaandbnever overflows. - Easy to type and remember. ( is also prime and is a common second modulus for double hashing.)
What it is not: safe in JavaScript number. exceeds , so a * b % MOD on doubles loses low bits. Use BigInt, or split one factor into 16-bit halves (shown in the code).
is the modulus for problems that need the number-theoretic transform (NTT, an FFT over ). An NTT of length needs a -th root of unity modulo , which exists exactly when . And
so is divisible by : transforms up to length million work. Its smallest primitive root is . It is also below , so sums of two residues fit comfortably in 32 bits. Other NTT-friendly primes: , (both with primitive root 3) — often combined via Garner. When a problem gives you 998244353, it is usually a hint that the intended solution multiplies polynomials.
6. Safe multiplication modulo a 64-bit modulus
With a modulus near (common in hashing, Miller–Rabin and CRT on big moduli), the product of two residues is near — far beyond 64 bits. Options, from easiest to fastest:
| Method | Where | Cost | Notes |
|---|---|---|---|
| Native big integers | Python int, JS BigInt, Java BigInteger | slow-ish (heap allocation per op) | Always correct; fine for a few million ops in Python |
| 128-bit intermediate | GCC/Clang unsigned __int128 | one hardware multiply + a 128-by-64 division | Not in MSVC (use _umul128 there); the 128-bit % is a library call (__umodti3), much slower than the multiply |
Math.multiplyHigh + reduction | Java 9+ | a few ops | Gives the high 64 bits; you still need to reduce a 128-bit value |
| Double-and-add ("Russian peasant") | any language | additions | Correct for any ; slow but portable |
long double trick | C/C++ on x86 | 2 multiplies | Estimate in 80-bit long double, then with 64-bit wrap-around and one correction; KACTL's modmul documents it for up to about . Platform-dependent (no 80-bit long double on MSVC or most ARM), so test it |
| Montgomery multiplication | crypto libraries, fast Miller–Rabin | a few multiplies, no division | Keeps numbers in "Montgomery form" ; the reduction step replaces division by with shifts by (Montgomery, 1985). Needs odd . OpenSSL's BN_mod_exp_mont uses it |
| Barrett reduction | arbitrary fixed | 2 multiplies + correction | Precomputes and estimates the quotient by multiplication (Barrett, 1986). Used when the modulus is fixed but not known at compile time |
Compilers already do Barrett-like reduction for you when the modulus is a compile-time constant: x % 1000000007 with a const modulus compiles to a multiply and a shift, not a div instruction. That is one reason to declare the modulus constexpr/final static.
7. Factorials, inverse factorials and
Counting problems need again and again. Division means inverses, and computing an inverse per query costs . Precompute instead, for :
fact[0] = 1,fact[i] = fact[i-1] * i % pfor .inv_fact[N] = power(fact[N], p - 2, p)— one exponentiation.inv_fact[i-1] = inv_fact[i] * i % p, going down from to 1. (Because .)
Then each query is in . With : , and . The derivation of the counting formulas, Pascal's triangle as an alternative, and Lucas' theorem for are in Counting DP and Combinatorics.
Factorials vanish once
For , contains the factor and is . Then becomes "0 times the inverse of 0" and the table method is wrong, even though may be non-zero. With and this never happens; with a small prime like it does, and you need Lucas' theorem.
RSA in one screen
RSA uses everything above. A toy instance with the numbers from the original textbook examples (also used on Wikipedia's RSA page):
- Key generation. Pick primes , . Public modulus . .
- Pick public exponent with .
- Private exponent — the extended-Euclid trace in section 2 above.
- Encrypt message : (fast exponentiation).
- Decrypt: . ✓
Why decryption works. for some . If , Euler's theorem gives . (If shares a factor with , the result still holds — check it modulo and modulo separately with Fermat and combine with CRT.) An attacker who could factor could compute and ; for 2048-bit nobody knows how to factor fast enough.
Where CRT speeds it up. Real implementations decrypt with and , exponentiate modulo and separately (numbers half as long, so each multiplication is about 4× cheaper and the exponents are half as long), then recombine with CRT. That is about a 4× speed-up and is what OpenSSL and every other RSA library does for private-key operations.
Toy RSA is not RSA
Textbook RSA (no padding, small primes, deterministic) is insecure: equal messages give equal ciphertexts, and small messages can be recovered with an integer -th root. Real systems use 2048+-bit moduli, OAEP padding for encryption and PSS for signatures, constant-time arithmetic and vetted libraries. See Cryptography for Engineers, Symmetric vs Asymmetric and Cryptography in the Real World.
The ladder: brute force → better → optimal
Ladder A:
| Rung | Method | Time | Why the next is better |
|---|---|---|---|
| 1 | Compute exactly, then % m | big-integer multiplications on numbers with up to bits | — The number has digits; impossible |
| 2 | Multiply-and-reduce times | word operations | Numbers stay small; still steps |
| 3 | Binary exponentiation | 60 steps for | |
| 4 | Reduce the exponent first ( or ) | Handles exponents that are themselves huge (given as strings, or towers) | |
| side | Precomputed powers / sliding window (k-ary) exponentiation | ~ squarings + multiplies | Constant-factor gain used by crypto libraries |
Ladder B: from residues (CRT)
| Rung | Method | Time | Notes |
|---|---|---|---|
| 1 | Try every from 0 to | Fine for Sunzi (105), hopeless for | |
| 2 | Sieve-style: step through checking the others | Better by one factor | |
| 3 | Pairwise merge with extended Euclid | Handles non-coprime moduli and detects contradictions | |
| 4 | Garner's mixed-radix | small-modulus ops | Avoids big intermediates; standard after multi-prime NTT |
Ladder C: for queries,
| Rung | Method | Precompute | Per query |
|---|---|---|---|
| 1 | Exact big-integer then mod | — | big multiplications |
| 2 | Pascal's triangle mod | time and memory | — fine to |
| 3 | Factorials + per-query Fermat inverse | ||
| 4 | Factorials + inverse factorials |
Correctness
Binary exponentiation. Invariant: at the top of each loop iteration, , where are the original inputs. Initially , , : true. If the low bit of is 1, write ; the loop sets , , , and . If the bit is 0, and the same holds without the multiplication. Reductions modulo preserve congruence. When , . The loop runs times.
Modular inverse by extended Euclid. Extended Euclid returns with (proved in Number Theory I). If , reducing modulo gives . If , no inverse exists (argument in the intuition section).
Inverse table. By induction on : . For , is non-zero (since is prime and ) and is correct by the hypothesis. From : , so .
CRT merge. Given and , with and . Necessity of was shown above. Sufficiency: let and . Then trivially, and (since is a multiple of ), so . Uniqueness modulo : two solutions differ by a common multiple of and , i.e. a multiple of . The code reduces modulo first, which changes by a multiple of and so keeps it a solution.
Totient formula. is multiplicative because, by CRT, corresponds to the pair for coprime , and is coprime to iff both components are coprime to their moduli. Combined with this gives the product formula. The result -= result / p update multiplies by exactly, because at that moment result , which is still divisible by (the factors removed so far did not include ).
Complexity
| Operation | Time | Space | Notes |
|---|---|---|---|
+, -, * mod (word-size ) | % by a run-time variable is a hardware division: tens of cycles, versus ~3 for a multiply | ||
power(a, b, m) | multiplications | 60 iterations for | |
| Inverse by Fermat | ~30 iterations for | ||
| Inverse by extended Euclid | Usually faster than Fermat in practice | ||
| Inverses of mod | |||
| Factorial + inverse-factorial tables | Then in | ||
| , one number | Faster with an SPF table or Pollard's rho | ||
| sieve | (or linear sieve) | ||
| CRT, equations | Plus big-number cost if exceeds 64 bits | ||
mulmod with __int128 | 128-by-64 division in software | ||
mulmod double-and-add | Portable fallback | ||
| Big-integer with -bit numbers | multiplications of -bit numbers | Schoolbook overall; Karatsuba/FFT multiplication lower it |
Implementation
Two code groups, each a complete program that checks itself against the numbers above and against brute force on random inputs. All were run on Python 3.12, Java 21, C++17 (g++) and Node 24.
Power, inverses, safe multiplication, factorial tables
MOD = 10**9 + 7
def power(a: int, b: int, m: int) -> int:
"""a^b mod m by binary exponentiation, b >= 0. (Python's pow(a, b, m) does the same.)"""
result, a = 1 % m, a % m
while b > 0:
if b & 1:
result = result * a % m
a = a * a % m
b >>= 1
return result
def ext_gcd(a: int, b: int) -> tuple[int, int, int]:
old_r, r, old_x, x, old_y, y = a, b, 1, 0, 0, 1
while r:
q = old_r // r
old_r, r = r, old_r - q * r
old_x, x = x, old_x - q * x
old_y, y = y, old_y - q * y
return old_r, old_x, old_y
def inv_fermat(a: int, p: int) -> int:
"""Inverse modulo a PRIME p; a must not be divisible by p."""
if a % p == 0:
raise ZeroDivisionError("0 has no inverse")
return power(a, p - 2, p)
def inv_euclid(a: int, m: int) -> int:
"""Inverse modulo any m >= 2 with gcd(a, m) == 1, else ValueError."""
g, x, _ = ext_gcd(a % m, m)
if g != 1:
raise ValueError(f"{a} has no inverse modulo {m} (gcd {g})")
return x % m
def inverse_table(n: int, p: int) -> list[int]:
"""inv[i] for 1 <= i <= n, p prime > n. O(n)."""
inv = [0, 1] + [0] * (n - 1)
for i in range(2, n + 1):
inv[i] = (p - (p // i) * inv[p % i] % p) % p
return inv
def mulmod(a: int, b: int, m: int) -> int:
"""Double-and-add: portable a*b mod m without wide products (shown for parity
with fixed-width languages; in Python, a * b % m is already exact)."""
a, b, result = a % m, b % m, 0
while b:
if b & 1:
result = (result + a) % m
a = (a + a) % m
b >>= 1
return result
class Binomial:
"""fact / inv_fact tables modulo a prime p, valid for n < p."""
def __init__(self, n: int, p: int = MOD):
self.p = p
self.fact = [1] * (n + 1)
for i in range(1, n + 1):
self.fact[i] = self.fact[i - 1] * i % p
self.inv_fact = [1] * (n + 1)
self.inv_fact[n] = power(self.fact[n], p - 2, p) # one exponentiation
for i in range(n, 0, -1):
self.inv_fact[i - 1] = self.inv_fact[i] * i % p
def C(self, n: int, k: int) -> int:
if k < 0 or k > n:
return 0
return self.fact[n] * self.inv_fact[k] % self.p * self.inv_fact[n - k] % self.p
if __name__ == "__main__":
import random
from math import comb, gcd
assert -7 % 3 == 2 and 7 % -3 == -2 # Python: sign of the divisor
assert power(3, 13, 7) == 3 and power(5, 0, 1) == 0 and power(7, 222, 10) == 9
assert power(2, 10**18, MOD) == pow(2, 10**18, MOD) == 719476260
assert inv_fermat(3, 7) == 5 and inv_euclid(17, 3120) == 2753 == pow(17, -1, 3120)
assert inv_euclid(3, 8) == 3 and power(3, 8 - 2, 8) == 1 # Fermat is wrong mod 8
try:
inv_euclid(2, 4)
assert False
except ValueError:
pass
assert (12 * inv_euclid(4, 7)) % 7 == 3 # "12 / 4" modulo 7
assert inverse_table(10, 11)[1:] == [1, 6, 4, 3, 9, 2, 8, 7, 5, 10]
inv = inverse_table(10**5, MOD)
assert all(i * inv[i] % MOD == 1 for i in range(1, 10**5 + 1))
m = (1 << 61) - 1
for _ in range(1000):
a, b = random.randrange(m), random.randrange(m)
assert mulmod(a, b, m) == a * b % m
mm = random.randrange(2, 10**6)
x = random.randrange(1, mm)
if gcd(x, mm) == 1:
assert x * inv_euclid(x, mm) % mm == 1
B = Binomial(10**5)
assert B.C(10, 3) == 120 and B.C(10**5, 5 * 10**4) == 149033233 == comb(10**5, 5 * 10**4) % MOD
assert B.C(5, 7) == 0
print("powmod / inverse tests passed")
import java.math.BigInteger;
import java.util.Random;
public class ModArith {
static final long MOD = 1_000_000_007L;
static long power(long a, long b, long m) { // m < 2^31 so products fit in long
long result = 1 % m;
a = Math.floorMod(a, m);
while (b > 0) {
if ((b & 1) == 1) result = result * a % m;
a = a * a % m;
b >>= 1;
}
return result;
}
/** a*b mod m for any 0 < m < 2^62, without overflow (double-and-add). */
static long mulmod(long a, long b, long m) {
a = Math.floorMod(a, m); b = Math.floorMod(b, m);
long result = 0;
while (b > 0) {
if ((b & 1) == 1) { result += a; if (result >= m) result -= m; }
a += a; if (a >= m) a -= m;
b >>= 1;
}
return result;
}
static long powerBig(long a, long b, long m) { // any m < 2^62
long result = 1 % m;
a = Math.floorMod(a, m);
while (b > 0) {
if ((b & 1) == 1) result = mulmod(result, a, m);
a = mulmod(a, a, m);
b >>= 1;
}
return result;
}
static long[] extGcd(long a, long b) {
long oldR = a, r = b, oldX = 1, x = 0, oldY = 0, y = 1;
while (r != 0) {
long q = oldR / r, t;
t = oldR - q * r; oldR = r; r = t;
t = oldX - q * x; oldX = x; x = t;
t = oldY - q * y; oldY = y; y = t;
}
return new long[]{oldR, oldX, oldY};
}
static long invFermat(long a, long p) {
if (Math.floorMod(a, p) == 0) throw new ArithmeticException("0 has no inverse");
return power(a, p - 2, p);
}
static long invEuclid(long a, long m) {
long[] e = extGcd(Math.floorMod(a, m), m);
if (e[0] != 1) throw new ArithmeticException(a + " has no inverse mod " + m);
return Math.floorMod(e[1], m);
}
static long[] inverseTable(int n, long p) {
long[] inv = new long[n + 1];
inv[1] = 1;
for (int i = 2; i <= n; i++) inv[i] = (p - (p / i) * inv[(int) (p % i)] % p) % p;
return inv;
}
static long[] fact, invFact;
static void buildBinomial(int n, long p) {
fact = new long[n + 1]; invFact = new long[n + 1];
fact[0] = 1;
for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % p;
invFact[n] = power(fact[n], p - 2, p);
for (int i = n; i > 0; i--) invFact[i - 1] = invFact[i] * i % p;
}
static long C(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}
static void check(boolean c, String m) { if (!c) throw new AssertionError(m); }
public static void main(String[] args) {
check(-7 % 3 == -1 && Math.floorMod(-7, 3) == 2, "java % sign");
check(power(3, 13, 7) == 3 && power(7, 222, 10) == 9 && power(5, 0, 1) == 0, "power");
check(power(2, 1_000_000_000_000_000_000L, MOD) == 719476260L, "2^1e18");
check(invFermat(3, 7) == 5 && invEuclid(17, 3120) == 2753, "inverses");
check(invEuclid(3, 8) == 3 && power(3, 6, 8) == 1, "fermat wrong mod 8");
boolean threw = false;
try { invEuclid(2, 4); } catch (ArithmeticException e) { threw = true; }
check(threw, "no inverse");
long[] t = inverseTable(10, 11);
check(java.util.Arrays.equals(java.util.Arrays.copyOfRange(t, 1, 11),
new long[]{1, 6, 4, 3, 9, 2, 8, 7, 5, 10}), "inv table");
Random rnd = new Random(7);
long m61 = (1L << 61) - 1;
BigInteger M = BigInteger.valueOf(m61);
for (int i = 0; i < 1000; i++) {
long a = Math.floorMod(rnd.nextLong(), m61), b = Math.floorMod(rnd.nextLong(), m61);
long want = BigInteger.valueOf(a).multiply(BigInteger.valueOf(b)).mod(M).longValue();
check(mulmod(a, b, m61) == want, "mulmod");
long e = Math.floorMod(rnd.nextLong(), 1_000_000_000_000L);
check(powerBig(a, e, m61) == BigInteger.valueOf(a).modPow(BigInteger.valueOf(e), M).longValue(), "powerBig");
}
buildBinomial(100_000, MOD);
check(C(10, 3) == 120 && C(100_000, 50_000) == 149033233L && C(5, 7) == 0, "binomial");
System.out.println("powmod / inverse tests passed");
}
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <random>
#include <stdexcept>
#include <tuple>
#include <vector>
using i64 = long long;
using u64 = unsigned long long;
using u128 = unsigned __int128;
constexpr i64 MOD = 1'000'000'007; // constexpr: the compiler turns % MOD into multiply+shift
i64 power(i64 a, i64 b, i64 m) { // m < 2^31 so a*a fits in 64 bits
i64 result = 1 % m;
a = ((a % m) + m) % m;
while (b > 0) {
if (b & 1) result = result * a % m;
a = a * a % m;
b >>= 1;
}
return result;
}
u64 mulmod(u64 a, u64 b, u64 m) { return (u64)((u128)a * b % m); } // any m < 2^64
u64 power64(u64 a, u64 b, u64 m) {
u64 result = 1 % m;
a %= m;
while (b) {
if (b & 1) result = mulmod(result, a, m);
a = mulmod(a, a, m);
b >>= 1;
}
return result;
}
std::tuple<i64, i64, i64> ext_gcd(i64 a, i64 b) {
i64 old_r = a, r = b, old_x = 1, x = 0, old_y = 0, y = 1;
while (r) {
i64 q = old_r / r, t;
t = old_r - q * r; old_r = r; r = t;
t = old_x - q * x; old_x = x; x = t;
t = old_y - q * y; old_y = y; y = t;
}
return {old_r, old_x, old_y};
}
i64 inv_fermat(i64 a, i64 p) {
if (a % p == 0) throw std::domain_error("0 has no inverse");
return power(a, p - 2, p);
}
i64 inv_euclid(i64 a, i64 m) {
auto [g, x, y] = ext_gcd(((a % m) + m) % m, m);
if (g != 1) throw std::domain_error("no inverse");
return ((x % m) + m) % m;
}
std::vector<i64> inverse_table(int n, i64 p) {
std::vector<i64> inv(n + 1, 0);
inv[1] = 1;
for (int i = 2; i <= n; ++i) inv[i] = (p - (p / i) * inv[p % i] % p) % p;
return inv;
}
struct Binomial {
std::vector<i64> fact, inv_fact;
explicit Binomial(int n) : fact(n + 1), inv_fact(n + 1) {
fact[0] = 1;
for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i % MOD;
inv_fact[n] = power(fact[n], MOD - 2, MOD);
for (int i = n; i > 0; --i) inv_fact[i - 1] = inv_fact[i] * i % MOD;
}
i64 C(int n, int k) const {
if (k < 0 || k > n) return 0;
return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}
};
int main() {
assert(-7 % 3 == -1 && ((-7 % 3) + 3) % 3 == 2); // C++: sign of the dividend
assert(power(3, 13, 7) == 3 && power(7, 222, 10) == 9 && power(5, 0, 1) == 0);
assert(power(2, 1000000000000000000LL, MOD) == 719476260);
assert(inv_fermat(3, 7) == 5 && inv_euclid(17, 3120) == 2753);
assert(inv_euclid(3, 8) == 3 && power(3, 6, 8) == 1);
bool threw = false;
try { inv_euclid(2, 4); } catch (const std::domain_error&) { threw = true; }
assert(threw);
auto t = inverse_table(10, 11);
assert((std::vector<i64>(t.begin() + 1, t.end()) == std::vector<i64>{1, 6, 4, 3, 9, 2, 8, 7, 5, 10}));
auto inv = inverse_table(100000, MOD);
for (int i = 1; i <= 100000; ++i) assert(i * inv[i] % MOD == 1);
// Fermat on a 61-bit Mersenne prime: a^(p-1) == 1 needs a safe mulmod
const u64 P61 = (1ULL << 61) - 1;
std::mt19937_64 rng(3);
for (int i = 0; i < 1000; ++i) {
u64 a = rng() % (P61 - 1) + 1;
assert(power64(a, P61 - 1, P61) == 1);
assert(mulmod(a, power64(a, P61 - 2, P61), P61) == 1);
}
Binomial B(100000);
assert(B.C(10, 3) == 120 && B.C(100000, 50000) == 149033233 && B.C(5, 7) == 0);
std::cout << "powmod / inverse tests passed\n";
}
const MOD = 1_000_000_007;
/** a*b mod m on doubles, exact for 0 <= a, b < m < 2^31: split b into 16-bit halves. */
function mulmodNum(a: number, b: number, m: number): number {
const hi = Math.floor(b / 65536), lo = b % 65536;
return (((a * hi) % m) * 65536 + a * lo) % m; // every intermediate < 2^53
}
function power(a: number, b: number, m: number): number { // m < 2^31, b < 2^53
let result = 1 % m;
a = ((a % m) + m) % m;
while (b > 0) {
if (b % 2 === 1) result = mulmodNum(result, a, m);
a = mulmodNum(a, a, m);
b = Math.floor(b / 2); // not >> : that truncates to 32 bits
}
return result;
}
function powerBig(a: bigint, b: bigint, m: bigint): bigint { // any size
let result = 1n % m;
a = ((a % m) + m) % m;
while (b > 0n) {
if (b & 1n) result = (result * a) % m;
a = (a * a) % m;
b >>= 1n;
}
return result;
}
function extGcd(a: bigint, b: bigint): [bigint, bigint, bigint] {
let oldR = a, r = b, oldX = 1n, x = 0n, oldY = 0n, y = 1n;
while (r !== 0n) {
const q = oldR / r;
[oldR, r] = [r, oldR - q * r];
[oldX, x] = [x, oldX - q * x];
[oldY, y] = [y, oldY - q * y];
}
return [oldR, oldX, oldY];
}
function invFermat(a: number, p: number): number {
if (a % p === 0) throw new RangeError("0 has no inverse");
return power(a, p - 2, p);
}
function invEuclid(a: bigint, m: bigint): bigint {
const [g, x] = extGcd(((a % m) + m) % m, m);
if (g !== 1n) throw new RangeError(`${a} has no inverse mod ${m}`);
return ((x % m) + m) % m;
}
function inverseTable(n: number, p: number): number[] {
const inv = new Array<number>(n + 1).fill(0);
inv[1] = 1;
for (let i = 2; i <= n; i++) inv[i] = (p - mulmodNum(Math.floor(p / i), inv[p % i], p)) % p;
return inv;
}
class Binomial {
fact: number[];
invFact: number[];
constructor(n: number) {
this.fact = new Array<number>(n + 1).fill(1);
for (let i = 1; i <= n; i++) this.fact[i] = mulmodNum(this.fact[i - 1], i, MOD);
this.invFact = new Array<number>(n + 1).fill(1);
this.invFact[n] = power(this.fact[n], MOD - 2, MOD);
for (let i = n; i > 0; i--) this.invFact[i - 1] = mulmodNum(this.invFact[i], i, MOD);
}
C(n: number, k: number): number {
if (k < 0 || k > n) return 0;
return mulmodNum(mulmodNum(this.fact[n], this.invFact[k], MOD), this.invFact[n - k], MOD);
}
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error("FAILED: " + msg);
}
check(-7 % 3 === -1 && ((-7 % 3) + 3) % 3 === 2, "JS % sign");
check((MOD - 1) * (MOD - 1) % MOD !== 1, "naive double product is wrong"); // loses bits past 2^53
check(mulmodNum(MOD - 1, MOD - 1, MOD) === 1, "safe product");
check(power(3, 13, 7) === 3 && power(7, 222, 10) === 9 && power(5, 0, 1) === 0, "power");
check(powerBig(2n, 10n ** 18n, BigInt(MOD)) === 719476260n, "2^1e18");
check(invFermat(3, 7) === 5 && invEuclid(17n, 3120n) === 2753n, "inverses");
check(invEuclid(3n, 8n) === 3n && power(3, 6, 8) === 1, "fermat wrong mod 8");
let threw = false;
try { invEuclid(2n, 4n); } catch { threw = true; }
check(threw, "no inverse");
check(inverseTable(10, 11).slice(1).join(",") === "1,6,4,3,9,2,8,7,5,10", "inv table");
const inv = inverseTable(100_000, MOD);
for (let i = 1; i <= 100_000; i++) check(mulmodNum(i, inv[i], MOD) === 1, "inv " + i);
const B = new Binomial(100_000);
check(B.C(10, 3) === 120 && B.C(100_000, 50_000) === 149033233 && B.C(5, 7) === 0, "binomial");
console.log("powmod / inverse tests passed");
Euler's totient, CRT, and RSA
from math import gcd
def ext_gcd(a: int, b: int) -> tuple[int, int, int]:
old_r, r, old_x, x, old_y, y = a, b, 1, 0, 0, 1
while r:
q = old_r // r
old_r, r = r, old_r - q * r
old_x, x = x, old_x - q * x
old_y, y = y, old_y - q * y
return old_r, old_x, old_y
def phi(n: int) -> int:
"""Euler's totient by trial division, O(sqrt n)."""
result, p = n, 2
while p * p <= n:
if n % p == 0:
while n % p == 0:
n //= p
result -= result // p
p += 1
if n > 1:
result -= result // n
return result
def phi_sieve(n: int) -> list[int]:
ph = list(range(n + 1))
for p in range(2, n + 1):
if ph[p] == p: # untouched so far: p is prime
for k in range(p, n + 1, p):
ph[k] -= ph[k] // p
return ph
def crt_pair(r1: int, m1: int, r2: int, m2: int):
"""Merge x = r1 (mod m1) and x = r2 (mod m2), moduli not necessarily coprime.
Returns (x, lcm) or None if inconsistent."""
g, p, _ = ext_gcd(m1, m2)
if (r2 - r1) % g:
return None
m2g = m2 // g
k = (r2 - r1) // g * p % m2g
lcm = m1 * m2g
return (r1 + m1 * k) % lcm, lcm
def crt(residues, moduli):
x, m = 0, 1
for r, mi in zip(residues, moduli):
merged = crt_pair(x, m, r % mi, mi)
if merged is None:
return None
x, m = merged
return x, m
if __name__ == "__main__":
import random
assert phi(36) == 12 and phi(97) == 96 and phi(3120) == 768 and phi(1) == 1
ps = phi_sieve(10**5)
assert ps[1:13] == [1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4]
assert all(ps[n] == phi(n) for n in range(1, 3000))
assert all(ps[n] == sum(gcd(k, n) == 1 for k in range(1, n + 1)) for n in range(1, 300))
assert pow(3, phi(10), 10) == 1 and pow(7, 222 % phi(10), 10) == 9
for _ in range(3000): # generalised Euler: a^b = a^(b mod phi + phi) for b >= phi
n, a = random.randrange(1, 500), random.randrange(0, 500)
b = random.randrange(phi(n), 5000)
assert pow(a, b, n) == pow(a, b % phi(n) + phi(n), n)
assert crt([2, 3, 2], [3, 5, 7]) == (23, 105) # Sunzi
assert crt([2, 8], [6, 10]) == (8, 30)
assert crt([1, 2], [4, 6]) is None
for _ in range(3000): # brute-force cross-check
m1, m2 = random.randrange(1, 60), random.randrange(1, 60)
r1, r2 = random.randrange(m1), random.randrange(m2)
got = crt_pair(r1, m1, r2, m2)
lcm = m1 * m2 // gcd(m1, m2)
sols = [x for x in range(lcm) if x % m1 == r1 and x % m2 == r2]
assert (got is None and not sols) or (got == (sols[0], lcm) and len(sols) == 1)
# RSA toy example
p, q, e = 61, 53, 17
n, ph_n = p * q, (p - 1) * (q - 1)
d = pow(e, -1, ph_n)
assert (n, ph_n, d) == (3233, 3120, 2753)
c = pow(65, e, n)
assert c == 2790 and pow(c, d, n) == 65
dp, dq, q_inv = d % (p - 1), d % (q - 1), pow(q, -1, p) # RSA-CRT decryption
mp, mq = pow(c, dp, p), pow(c, dq, q)
assert (mq + q * ((mp - mq) * q_inv % p)) == 65
assert all(pow(pow(m, e, n), d, n) == m for m in range(n)) # every message, even non-coprime
print("totient / CRT / RSA tests passed")
import java.math.BigInteger;
import java.util.Random;
public class TotientCrt {
static long[] extGcd(long a, long b) {
long oldR = a, r = b, oldX = 1, x = 0, oldY = 0, y = 1;
while (r != 0) {
long q = oldR / r, t;
t = oldR - q * r; oldR = r; r = t;
t = oldX - q * x; oldX = x; x = t;
t = oldY - q * y; oldY = y; y = t;
}
return new long[]{oldR, oldX, oldY};
}
static long phi(long n) {
long result = n;
for (long p = 2; p * p <= n; p++) {
if (n % p != 0) continue;
while (n % p == 0) n /= p;
result -= result / p;
}
if (n > 1) result -= result / n;
return result;
}
static int[] phiSieve(int n) {
int[] ph = new int[n + 1];
for (int i = 0; i <= n; i++) ph[i] = i;
for (int p = 2; p <= n; p++)
if (ph[p] == p)
for (int k = p; k <= n; k += p) ph[k] -= ph[k] / p;
return ph;
}
/** a*b mod m without overflow for 0 < m < 2^62. */
static long mulmod(long a, long b, long m) {
a = Math.floorMod(a, m); b = Math.floorMod(b, m);
long r = 0;
while (b > 0) {
if ((b & 1) == 1) { r += a; if (r >= m) r -= m; }
a += a; if (a >= m) a -= m;
b >>= 1;
}
return r;
}
/** Merge x=r1 (mod m1), x=r2 (mod m2). Returns {x, lcm} or null. lcm must fit in 62 bits. */
static long[] crtPair(long r1, long m1, long r2, long m2) {
long[] e = extGcd(m1, m2);
long g = e[0], p = e[1];
if ((r2 - r1) % g != 0) return null;
long m2g = m2 / g;
long k = mulmod((r2 - r1) / g, p, m2g); // safe even when the product is large
long lcm = m1 * m2g;
return new long[]{Math.floorMod(r1 + mulmod(m1, k, lcm), lcm), lcm};
}
static long[] crt(long[] rs, long[] ms) {
long x = 0, m = 1;
for (int i = 0; i < rs.length; i++) {
long[] merged = crtPair(x, m, Math.floorMod(rs[i], ms[i]), ms[i]);
if (merged == null) return null;
x = merged[0]; m = merged[1];
}
return new long[]{x, m};
}
static long gcd(long a, long b) { while (b != 0) { long t = a % b; a = b; b = t; } return a; }
static void check(boolean c, String m) { if (!c) throw new AssertionError(m); }
public static void main(String[] args) {
check(phi(36) == 12 && phi(97) == 96 && phi(3120) == 768 && phi(1) == 1, "phi");
int[] ps = phiSieve(100_000);
for (int n = 1; n < 3000; n++) check(ps[n] == phi(n), "sieve " + n);
long[] s = crt(new long[]{2, 3, 2}, new long[]{3, 5, 7});
check(s[0] == 23 && s[1] == 105, "sunzi");
long[] t = crt(new long[]{2, 8}, new long[]{6, 10});
check(t[0] == 8 && t[1] == 30, "non-coprime");
check(crt(new long[]{1, 2}, new long[]{4, 6}) == null, "inconsistent");
// large coprime moduli near 1e9: the lcm is ~1e18, intermediate products would overflow
long[] big = crt(new long[]{123456789, 987654321}, new long[]{1_000_000_007L, 998_244_353L});
check(big[0] % 1_000_000_007L == 123456789 && big[0] % 998_244_353L == 987654321, "big crt");
Random rnd = new Random(5);
for (int it = 0; it < 3000; it++) {
long m1 = 1 + rnd.nextInt(59), m2 = 1 + rnd.nextInt(59);
long r1 = rnd.nextInt((int) m1), r2 = rnd.nextInt((int) m2);
long[] got = crtPair(r1, m1, r2, m2);
long lcm = m1 / gcd(m1, m2) * m2;
long first = -1;
for (long x = 0; x < lcm; x++) if (x % m1 == r1 && x % m2 == r2) { first = x; break; }
check(first == -1 ? got == null : got != null && got[0] == first && got[1] == lcm, "crt brute");
}
// RSA toy example
long p = 61, q = 53, e = 17, n = p * q, ph = (p - 1) * (q - 1);
long d = Math.floorMod(extGcd(e, ph)[1], ph);
check(n == 3233 && ph == 3120 && d == 2753, "rsa keys");
BigInteger N = BigInteger.valueOf(n);
BigInteger c = BigInteger.valueOf(65).modPow(BigInteger.valueOf(e), N);
check(c.longValue() == 2790 && c.modPow(BigInteger.valueOf(d), N).longValue() == 65, "rsa");
System.out.println("totient / CRT / RSA tests passed");
}
}
#include <cassert>
#include <iostream>
#include <numeric>
#include <optional>
#include <random>
#include <tuple>
#include <utility>
#include <vector>
using i64 = long long;
using i128 = __int128;
std::tuple<i64, i64, i64> ext_gcd(i64 a, i64 b) {
i64 old_r = a, r = b, old_x = 1, x = 0, old_y = 0, y = 1;
while (r) {
i64 q = old_r / r, t;
t = old_r - q * r; old_r = r; r = t;
t = old_x - q * x; old_x = x; x = t;
t = old_y - q * y; old_y = y; y = t;
}
return {old_r, old_x, old_y};
}
i64 phi(i64 n) {
i64 result = n;
for (i64 p = 2; p * p <= n; ++p) {
if (n % p) continue;
while (n % p == 0) n /= p;
result -= result / p;
}
if (n > 1) result -= result / n;
return result;
}
std::vector<int> phi_sieve(int n) {
std::vector<int> ph(n + 1);
std::iota(ph.begin(), ph.end(), 0);
for (int p = 2; p <= n; ++p)
if (ph[p] == p)
for (int k = p; k <= n; k += p) ph[k] -= ph[k] / p;
return ph;
}
// Merge x = r1 (mod m1), x = r2 (mod m2); returns {x, lcm} or nullopt. lcm must fit in i64.
std::optional<std::pair<i64, i64>> crt_pair(i64 r1, i64 m1, i64 r2, i64 m2) {
auto [g, p, q] = ext_gcd(m1, m2);
if ((r2 - r1) % g != 0) return std::nullopt;
i64 m2g = m2 / g;
i64 k = (i64)((i128)((r2 - r1) / g) * p % m2g); // 128-bit product, no overflow
if (k < 0) k += m2g;
i64 lcm = m1 * m2g;
i64 x = (i64)(((i128)r1 + (i128)m1 * k) % lcm);
if (x < 0) x += lcm;
return std::make_pair(x, lcm);
}
std::optional<std::pair<i64, i64>> crt(const std::vector<i64>& rs, const std::vector<i64>& ms) {
i64 x = 0, m = 1;
for (size_t i = 0; i < rs.size(); ++i) {
auto merged = crt_pair(x, m, ((rs[i] % ms[i]) + ms[i]) % ms[i], ms[i]);
if (!merged) return std::nullopt;
std::tie(x, m) = *merged;
}
return std::make_pair(x, m);
}
i64 power(i64 a, i64 b, i64 m) {
i64 r = 1 % m;
a %= m;
while (b) { if (b & 1) r = r * a % m; a = a * a % m; b >>= 1; }
return r;
}
int main() {
assert(phi(36) == 12 && phi(97) == 96 && phi(3120) == 768 && phi(1) == 1);
auto ps = phi_sieve(100000);
for (int n = 1; n < 3000; ++n) assert(ps[n] == phi(n));
auto s = crt({2, 3, 2}, {3, 5, 7});
assert(s && s->first == 23 && s->second == 105);
auto t = crt({2, 8}, {6, 10});
assert(t && t->first == 8 && t->second == 30);
assert(!crt({1, 2}, {4, 6}));
auto big = crt({123456789, 987654321}, {1000000007LL, 998244353LL});
assert(big && big->first % 1000000007LL == 123456789 && big->first % 998244353LL == 987654321);
std::mt19937 rng(5);
for (int it = 0; it < 3000; ++it) {
i64 m1 = 1 + rng() % 59, m2 = 1 + rng() % 59, r1 = rng() % m1, r2 = rng() % m2;
auto got = crt_pair(r1, m1, r2, m2);
i64 lcm = m1 / std::gcd(m1, m2) * m2, first = -1;
for (i64 x = 0; x < lcm; ++x) if (x % m1 == r1 && x % m2 == r2) { first = x; break; }
assert(first == -1 ? !got : (got && got->first == first && got->second == lcm));
}
// RSA toy example
i64 p = 61, q = 53, e = 17, n = p * q, ph = (p - 1) * (q - 1);
i64 d = (std::get<1>(ext_gcd(e, ph)) % ph + ph) % ph;
assert(n == 3233 && ph == 3120 && d == 2753);
i64 c = power(65, e, n);
assert(c == 2790 && power(c, d, n) == 65);
for (i64 m = 0; m < n; ++m) assert(power(power(m, e, n), d, n) == m);
std::cout << "totient / CRT / RSA tests passed\n";
}
function extGcd(a: bigint, b: bigint): [bigint, bigint, bigint] {
let oldR = a, r = b, oldX = 1n, x = 0n, oldY = 0n, y = 1n;
while (r !== 0n) {
const q = oldR / r;
[oldR, r] = [r, oldR - q * r];
[oldX, x] = [x, oldX - q * x];
[oldY, y] = [y, oldY - q * y];
}
return [oldR, oldX, oldY];
}
const mod = (a: bigint, m: bigint): bigint => ((a % m) + m) % m; // bigint % truncates like C
function phi(n: number): number {
let result = n;
for (let p = 2; p * p <= n; p++) {
if (n % p !== 0) continue;
while (n % p === 0) n /= p;
result -= result / p;
}
if (n > 1) result -= result / n;
return result;
}
function phiSieve(n: number): Int32Array {
const ph = new Int32Array(n + 1);
for (let i = 0; i <= n; i++) ph[i] = i;
for (let p = 2; p <= n; p++)
if (ph[p] === p) for (let k = p; k <= n; k += p) ph[k] -= ph[k] / p;
return ph;
}
/** Merge x = r1 (mod m1), x = r2 (mod m2). Returns [x, lcm] or null. Arbitrary size. */
function crtPair(r1: bigint, m1: bigint, r2: bigint, m2: bigint): [bigint, bigint] | null {
const [g, p] = extGcd(m1, m2);
if ((r2 - r1) % g !== 0n) return null;
const m2g = m2 / g;
const k = mod(((r2 - r1) / g) * p, m2g);
const lcm = m1 * m2g;
return [mod(r1 + m1 * k, lcm), lcm];
}
function crt(rs: bigint[], ms: bigint[]): [bigint, bigint] | null {
let x = 0n, m = 1n;
for (let i = 0; i < rs.length; i++) {
const merged = crtPair(x, m, mod(rs[i], ms[i]), ms[i]);
if (merged === null) return null;
[x, m] = merged;
}
return [x, m];
}
function powerBig(a: bigint, b: bigint, m: bigint): bigint {
let r = 1n % m;
a = mod(a, m);
while (b > 0n) {
if (b & 1n) r = (r * a) % m;
a = (a * a) % m;
b >>= 1n;
}
return r;
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error("FAILED: " + msg);
}
check(phi(36) === 12 && phi(97) === 96 && phi(3120) === 768 && phi(1) === 1, "phi");
const ps = phiSieve(100_000);
for (let n = 1; n < 3000; n++) check(ps[n] === phi(n), "sieve " + n);
const s = crt([2n, 3n, 2n], [3n, 5n, 7n]);
check(s !== null && s[0] === 23n && s[1] === 105n, "sunzi");
const t = crt([2n, 8n], [6n, 10n]);
check(t !== null && t[0] === 8n && t[1] === 30n, "non-coprime");
check(crt([1n, 2n], [4n, 6n]) === null, "inconsistent");
const gcdN = (a: number, b: number): number => (b === 0 ? a : gcdN(b, a % b));
for (let it = 0; it < 3000; it++) {
const m1 = 1 + Math.floor(Math.random() * 59), m2 = 1 + Math.floor(Math.random() * 59);
const r1 = Math.floor(Math.random() * m1), r2 = Math.floor(Math.random() * m2);
const got = crtPair(BigInt(r1), BigInt(m1), BigInt(r2), BigInt(m2));
const lcm = (m1 / gcdN(m1, m2)) * m2;
let first = -1;
for (let x = 0; x < lcm; x++) if (x % m1 === r1 && x % m2 === r2) { first = x; break; }
check(first === -1 ? got === null : got !== null && got[0] === BigInt(first) && got[1] === BigInt(lcm), "crt brute");
}
// RSA toy example
const p = 61n, q = 53n, e = 17n, n = p * q, ph = (p - 1n) * (q - 1n);
const d = mod(extGcd(e, ph)[1], ph);
check(n === 3233n && ph === 3120n && d === 2753n, "rsa keys");
const c = powerBig(65n, e, n);
check(c === 2790n && powerBig(c, d, n) === 65n, "rsa");
console.log("totient / CRT / RSA tests passed");
Real-world uses
- Public-key cryptography. RSA encryption and signatures are and with 2048–4096-bit . Diffie–Hellman key exchange is . OpenSSL computes these with Montgomery multiplication and sliding-window exponentiation (
BN_mod_exp_mont) and decrypts with the CRT shortcut (,qInv— the fields of a PKCS #1 private key are exactly these values, defined in RFC 8017). Elliptic-curve cryptography (ECDSA, Ed25519, X25519) does field arithmetic modulo primes such as , chosen so that reduction is a few shifts and adds. - Post-quantum cryptography. ML-KEM (Kyber, FIPS 203) multiplies polynomials with an NTT modulo , a prime with , so 256th roots of unity exist.
- Hashing. Polynomial rolling hashes (String Hashing), universal hashing (Carter and Wegman, 1979), and the bucket index
hash % capacityin every hash table. - Pseudo-random generators. A linear congruential generator is .
java.util.Randomuses and (documented in its Javadoc); the "minimal standard" generator of Park and Miller (1988) uses , . - Check digits. ISBN-10 uses a weighted sum modulo 11 (hence the "X" for 10); IBAN uses ISO 7064 MOD 97-10 — the rearranged account number, read as a huge integer, must be , computed piecewise exactly as in "reduce as you go"; credit-card numbers use the Luhn algorithm modulo 10.
- Calendars and clocks. Day-of-week formulas (Zeller's congruence), ring buffers (
(head + 1) % capacity, see Queues & Circular Buffers), round-robin schedulers, sharding byid % shards(see System Design Math). - Exact big-integer and polynomial arithmetic. Computer-algebra systems compute determinants and polynomial GCDs modulo several primes and reconstruct the exact answer with CRT, which avoids huge intermediate numbers.
Pitfalls & edge cases
- Negative remainders in C++/Java/JS.
(a - b) % mcan be negative. Normalise with((x % m) + m) % morMath.floorMod. - Overflow before the
%. In C++/Java,a * b % MODwithintoperands overflows before the reduction. Make at least one operand 64-bit:1LL * a * b % MOD. - JavaScript doubles.
a * b % 1000000007is silently wrong oncea * b > 2^53(about ). The TypeScript code above shows the check failing on purpose. 1 % mfor . is 0, not 1. Initialiseresult = 1 % m.- Fermat with a composite modulus. Wrong silently (inverse of 3 mod 8 example). Use extended Euclid unless you know is prime.
- Inverse of 0 or of a non-coprime value. Fermat returns 0 for instead of failing. Check , or check the result:
a * inv % m == 1. - Exponent reduced modulo instead of . , and only when . If and but , the reduced form gives instead of .
- Comparing or taking
maxof residues. After reduction, "bigger" means nothing: the true value becomes 1. If a problem needs the maximum of something and the answer modulo , compare the true values (or logarithms) and reduce only the output. - Dividing a residue by an integer with
/.(sum % MOD) / 2is wrong; usesum % MOD * inv2 % MODwhereinv2 = (MOD + 1) / 2. - Factorials for . The table method breaks (warning above). Lucas' theorem or Kummer's theorem instead.
- CRT overflow. The LCM of moduli can exceed 64 bits; and
(r2 - r1) / g * pcan overflow even when the LCM fits. Use 128-bit products ormulmod, as the code does. - Modulus not prime in a "for every inverse" algorithm. Gaussian elimination modulo or polynomial division modulo need a field; with composite some pivots have no inverse.
Variations
- Discrete logarithms and modular square roots. Solve with baby-step giant-step in — see Number Theory II. For , Euler's criterion () says whether a root exists, and the Tonelli–Shanks algorithm finds it (Henri Cohen, A Course in Computational Algebraic Number Theory, §1.5).
- Primitive roots. A generator whose powers hit every non-zero residue modulo ; needed for NTT and Diffie–Hellman. Also Number Theory II.
- Miller–Rabin. A primality test that is a few modular exponentiations; deterministic for 64-bit inputs with a fixed set of bases. See Randomized Algorithms.
- Lucas' theorem. for by writing and in base . Combinatorics.
- Matrices modulo . Matrix exponentiation computes linear recurrences in (Matrix Exponentiation); Gaussian elimination modulo a prime solves linear systems exactly (Linear Algebra).
- Modular arithmetic on expectations. "Output the expected value as " — probability problems use inverses to represent fractions exactly. See Probability & Expected Value and Probability DP.
- Wilson's theorem. exactly when is prime — elegant, useless as a primality test (computing is slow), handy for computing with large .
- Hensel lifting. Solve a congruence modulo , then lift the solution to modulo — used for inverses modulo in Montgomery setup (Newton's iteration doubles the correct bits each step).
Practice ladder
Each problem is described in my own words; follow the link for the full statement.
1. Pow(x, n) (LeetCode 50) — Real-number power with an integer exponent that may be negative. Binary exponentiation without the modulus.
Hint
Square-and-multiply; for use and (careful: overflows a 32-bit int).
2. Exponentiation (CSES 1095) — Many queries . The plain powmod.
Hint
The power function above, once per query. Note by the problem's convention.
3. Count Good Numbers (LeetCode 1922) — Count digit strings of length up to where even positions hold even digits and odd positions hold primes. Teaches "the answer is a product of powers".
Solution
Even indices: 5 choices each, of them. Odd indices: 4 choices (2, 3, 5, 7), of them. Answer .
MOD = 10**9 + 7
def count_good_numbers(n: int) -> int:
return pow(5, (n + 1) // 2, MOD) * pow(4, n // 2, MOD) % MOD
assert count_good_numbers(1) == 5 and count_good_numbers(4) == 400 and count_good_numbers(50) == 564908303
4. Count Collisions of Monkeys on a Polygon (LeetCode 2550) — Complement counting with a huge exponent. Teaches the negative-remainder trap.
Hint
Only the two "everyone moves the same way" outcomes avoid a collision: . In Java/C++ write (pow(2, n) - 2 + MOD) % MOD.
5. Binomial Coefficients (CSES 1079) — queries of , . The factorial + inverse-factorial tables.
Solution
Build fact and inv_fact up to once (the Binomial class above), then answer each query in .
MOD = 10**9 + 7
def binomial_queries(queries, n_max=10**6):
fact = [1] * (n_max + 1)
for i in range(1, n_max + 1):
fact[i] = fact[i - 1] * i % MOD
inv_fact = [1] * (n_max + 1)
inv_fact[n_max] = pow(fact[n_max], MOD - 2, MOD)
for i in range(n_max, 0, -1):
inv_fact[i - 1] = inv_fact[i] * i % MOD
return [fact[a] * inv_fact[b] % MOD * inv_fact[a - b] % MOD for a, b in queries]
assert binomial_queries([(5, 3), (8, 1), (9, 5)], n_max=10) == [10, 8, 126]
6. Concatenation of Consecutive Binary Numbers (LeetCode 1680) — The value of "1" + "10" + "11" + … up to in binary, modulo . Teaches reducing as you shift.
Hint
ans = ((ans << bits(i)) + i) % MOD, where bits(i) increases by one exactly when is a power of two.
7. Super Pow (LeetCode 372) — with given as an array of digits. Teaches exponent handling without reducing modulo , or with it.
Solution
Process digits left to right: . No totient needed. ( is composite, so do not reduce the exponent modulo 1336.)
def super_pow(a: int, digits: list[int]) -> int:
M = 1337
result = 1
for d in digits:
result = pow(result, 10, M) * pow(a, d, M) % M
return result
assert super_pow(2, [3]) == 8 and super_pow(2, [1, 0]) == 1024
assert super_pow(2147483647, [2, 0, 0]) == 1198
8. Bouquet (AtCoder ABC 156 D) — Count non-empty subsets of flowers whose size is neither nor . Teaches for huge and small .
Hint
. Compute in with one inverse of . Normalise the subtraction.
9. Exponentiation II (CSES 1712) — . Teaches Fermat exponent reduction modulo .
Solution
Compute , then . This is valid when (Fermat). When the answer is 0 unless the exponent is 0 (that is, ), and reducing the exponent would wrongly turn a positive multiple of into 0 — so handle that case first.
MOD = 10**9 + 7
def tower(a: int, b: int, c: int) -> int:
if a % MOD == 0: # 0^(b^c): 1 if the exponent is 0, else 0
return 1 if (b == 0 and c > 0) else 0
return pow(a, pow(b, c, MOD - 1), MOD)
assert tower(3, 7, 1) == 2187 and tower(15, 2, 2) == 50625 and tower(3, 4, 5) == pow(3, 4**5, MOD)
assert tower(2, 0, 5) == 1 # b^c = 0, so 2^0 = 1
10. Throne (AtCoder ABC 186 E) — Chairs in a circle; how many steps of size bring you from position to the throne at 0? A linear congruence .
Hint
Let . If , answer . Otherwise divide , , by and (extended Euclid, the modulus is not prime).
11. Remainders Game (Codeforces 687B) — Knowing for given , can you always deduce ? CRT reasoning without solving anything.
Hint
The residues determine modulo . So the answer is "yes" iff — compute the LCM modulo cleverly, or check prime powers of one by one.
12. General Chinese Remainder (Kattis) — Merge two congruences with possibly non-coprime moduli, or report "no solution". Direct application of crt_pair.
Hint
The code above, with 128-bit intermediate products (moduli up to , so the LCM fits in 64 bits but products of intermediates may not).
13. GCD Table (Codeforces 338D) — Decide whether a sequence appears in a row of the huge table . Hard: CRT over congruences with huge moduli plus verification.
Hint
The row must be (or a multiple; take the LCM itself). The column must satisfy for each — solve with general CRT. Then verify for every , and the bounds.
Common mistakes & interview follow-ups
"Why do problems use ?" Prime (inverses exist), sums of two residues fit in int32, products fit in int64.
"How do you divide modulo ?" Multiply by the inverse: Fermat for prime , extended Euclid otherwise. Mention that it exists only for .
"Complexity of fast exponentiation?" multiplications. If asked for bit complexity with -bit numbers: multiplications of -bit numbers.
"Implement pow without recursion and handle negative exponents." Iterative square-and-multiply; for negative exponents, invert the base (only meaningful modulo when the inverse exists).
"Product of two 63-bit numbers modulo a 63-bit number in Java?" Math.multiplyHigh plus a reduction, BigInteger, or double-and-add. In C++ unsigned __int128. Name Montgomery as the fast production answer.
"Explain RSA in two minutes." , , encrypt , decrypt , correctness by Euler, security by the hardness of factoring. Mention padding and CRT decryption to sound like you have shipped it.
"Solve , ." , is odd: no solution. Interviewers like this trap because people apply coprime CRT blindly.
Mistakes interviewers watch for: a * b % m overflowing in int; negative %; reducing an exponent modulo ; Fermat on composite moduli; forgetting 1 % m; comparing residues; dividing residues with /.
Quick quiz
1. What does -13 % 5 return in Python, Java, C++ and JavaScript?
Answer
Python: 2. Java, C++, JavaScript: −3. (Both satisfy : Python uses , the others .)
2. How many loop iterations does binary exponentiation do for ?
Answer
.
3. Find by Fermat and by inspection.
Answer
Fermat: . Inspection: , so the inverse is 8.
4. ?
Answer
.
5. Solve , .
Answer
, , , , . Check: . Unique modulo 36.
6. Why can't you compute with factorial tables modulo 7?
Answer
and contain the factor 7 (twice and once), so they are and has no inverse. Use Lucas' theorem: , , so . (Indeed .)
Further reading / sources
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed. — Chapter 31: §31.3–31.4 (modular arithmetic, solving linear congruences), §31.5 (CRT), §31.6 (powers of an element, repeated squaring), §31.7 (RSA), §31.8 (primality testing).
- Donald E. Knuth, TAOCP Vol. 2 — §4.3.2 (modular arithmetic for multiple precision, Garner's method), §4.6.3 (evaluation of powers).
- R. L. Rivest, A. Shamir, L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM 21(2), 1978.
- Peter L. Montgomery, "Modular Multiplication Without Trial Division", Mathematics of Computation 44(170), 1985. Paul Barrett, "Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor", CRYPTO '86.
- RFC 8017, PKCS #1: RSA Cryptography Specifications Version 2.2 (2016) — the CRT private-key representation and OAEP/PSS.
- Harvey L. Garner, "The Residue Number System", IRE Transactions on Electronic Computers, 1959.
- cp-algorithms: Binary exponentiation, Modular inverse, Euler's totient, Chinese Remainder Theorem, Garner's algorithm, Montgomery multiplication.
- Language references for
%: the C++ standard ([expr.mul], truncation since C++11), the Java Language Specification §15.17.3, Python's Numeric types notes, and MDN's Remainder (%).
Lessons: previous — Number Theory I · next — Number Theory II · module — Math for Algorithms · course — DSA: Zero to Mastery.
Related Archon pages: Counting DP · Matrix Exponentiation · String Hashing · Randomized Algorithms · Bit Manipulation · Cryptography for Engineers · Hash Tables.