Number theory for programmers

Computer Science and Engineering (B.E./B.Tech) · Algorithms · free study notes for exams, placements and interviews

In short

Number theory for programmers is the toolkit of integer arithmetic that algorithm problems demand: divisibility, GCD/LCM, modular arithmetic, primes, factorisation, congruences and counting with divisors. It matters because answers in competitive and interview problems are almost always asked "modulo 10⁹+7", because cryptography (RSA, Diffie-Hellman, UPI signing, Aadhaar and GSTIN check digits) is built on it, and because an O(√n) or O(log n) number-theoretic trick usually replaces an O(n) loop that times out. It is examined in GATE CS (Discrete Mathematics and Algorithms), in university papers on Design and Analysis of Algorithms and Discrete Structures, and in placement tests at TCS NQT/CodeVita, Infosys, Amazon, Microsoft, Google, Goldman Sachs, Media.net and D. E. Shaw. The topic is small in syllabus but very high in marks-per-hour because every result is a one-line formula with a short proof.

Explained

Divisibility, GCD and LCM

Divisibility: a | b means b = a·k for some integer k. Basic facts: if a | b and a | c then a | (bx + cy) for all integers x, y.
Division algorithm: for any a and b > 0 there are unique q, r with a = bq + r and 0 ≤ r < b. This single statement underlies Euclid's algorithm and all modular arithmetic.
GCD by Euclid: gcd(a, b) = gcd(b, a mod b), with gcd(a, 0) = a. Runs in O(log min(a, b)) steps; the worst case is consecutive Fibonacci numbers (Lamé's theorem), so about 1.44·log₂ n steps.
Binary (Stein's) GCD replaces the modulo with shifts and subtractions — same O(log²) bit cost but no division instruction; used in embedded and crypto libraries.
Extended Euclid returns (g, x, y) with ax + by = g = gcd(a, b) — Bézout's identity. This is how modular inverses and linear Diophantine equations are solved.
LCM: lcm(a, b) = a·b / gcd(a, b). Compute as a / g * b to avoid overflow. gcd and lcm are both associative, so extend to arrays by folding.
Coprime: gcd(a, b) = 1. Consequences: gcd(a, bc) = 1 if a is coprime to both; if a | bc and gcd(a, b) = 1 then a | c (Euclid's lemma).
Divisibility rules (useful for digit problems): by 3 or 9 — digit sum; by 11 — alternating digit sum; by 2^k — last k digits; by 7 — no simple rule, use modulo.

Modular arithmetic and fast exponentiation

Congruence: a ≡ b (mod m) means m | (a − b). Addition, subtraction and multiplication are well defined on residue classes: (a+b) mod m, (a−b+m) mod m, (a·b) mod m.
Division is not well defined — you multiply by the modular inverse, which exists only when gcd(a, m) = 1.
Why 10⁹+7: it is prime, so every non-zero residue has an inverse (Fermat), and two residues multiply to under 10¹⁸, which fits a signed 64-bit long long. 998244353 is the other favourite because it is 119·2²³ + 1, giving a 2²³-th root of unity for NTT.
Binary exponentiation (modpow): aⁿ mod m in O(log n) multiplications — square the base, halve the exponent, multiply in when the current bit of n is 1.
Modular multiplication overflow: if m can reach 10¹⁸, a·b overflows 64 bits; use __int128 in C++, Math.multiplyHigh/BigInteger in Java, or Python's native big integers (pow(a, b, m)).
Negative remainders: C, C++ and Java give −7 % 3 = −1; Python and the mathematical convention give 2. Always normalise with ((x % m) + m) % m.
Linear congruence ax ≡ b (mod m) has a solution iff g = gcd(a, m) divides b, and then exactly g solutions modulo m, found by dividing through by g and inverting a/g.

Inverses, Fermat, Euler and orders

Fermat's little theorem: for prime p and a not divisible by p, a^p−1 ≡ 1 (mod p). Hence a⁻¹ ≡ a^p−2 (mod p) — the one-liner used everywhere.
Euler's totient φ(n) counts integers in [1, n] coprime to n. It is multiplicative: φ(p^k) = p^k − p^k−1, so φ(n) = n·Π(1 − 1/p) over distinct primes p | n.
Euler's theorem: a^φ(n) ≡ 1 (mod n) when gcd(a, n) = 1; so a⁻¹ ≡ a^φ(n)−1 (mod n) for composite moduli too.
Extended-Euclid inverse works whenever gcd(a, m) = 1, prime or not, and is the safe general method.
Batch inverses: inverses of 1…n modulo prime p in O(n) by inv[i] = −(p/i)·inv[p mod i] mod p; or build factorials and inverse factorials once.
Multiplicative order ord_m(a) is the least k > 0 with a^k ≡ 1; it always divides φ(m). If ord_m(a) = φ(m), a is a primitive root and generates the whole group — primitive roots exist exactly for m = 1, 2, 4, p^k, 2p^k (p odd prime).
Euler's theorem for huge exponents: a^b mod m with b given as a long string — reduce b modulo φ(m); when gcd(a, m) ≠ 1 use the generalised form a^b ≡ a^{φ(m) + b mod φ(m)} for b ≥ log₂ m.
Wilson's theorem: (p−1)! ≡ −1 (mod p) iff p is prime — elegant, but useless as a primality test.

Primes: sieves, primality testing and factorisation

Trial division for primality: test divisors up to √n only, since a composite n has a factor ≤ √n. O(√n).
Sieve of Eratosthenes: mark multiples of each prime starting at p²; time O(n log log n), memory O(n) bits. Standard limit on a judge: n ≈ 10⁷–10⁸ with a bitset.
Linear sieve computes the smallest prime factor (SPF) for every number in O(n), giving instant factorisation of any n ≤ limit and values of φ, μ, d(n), σ(n) along the way.
Segmented sieve: to list primes in [L, R] with R up to 10¹², sieve primes to √R, then mark their multiples inside a window of length R − L + 1. Memory depends on the window, not R.
Fermat test: pick random a, check aⁿ⁻¹ ≡ 1 (mod n). Fails on Carmichael numbers (561, 1105, 1729 — Ramanujan's taxicab number is the third Carmichael number).
Miller-Rabin: write n − 1 = d·2^s; n is composite unless a^d ≡ ±1 or some a^{d·2^r} ≡ −1. Probabilistic in general, but deterministic if you test the fixed bases {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} for any 64-bit n.
Pollard's rho factorises in about O(n^1/4) using Floyd/Brent cycle detection on x → x² + c with gcd(|x − y|, n). Combined with Miller-Rabin it fully factorises 10¹⁸ in milliseconds.
AKS proves primality in deterministic polynomial time (theory question only — too slow in practice).
Prime counting: π(n) ≈ n / ln n (prime number theorem); π(100) = 25, π(10⁶) = 78,498. The n-th prime is about n·ln n.
Fundamental theorem of arithmetic: every integer > 1 has a unique prime factorisation — the basis of every divisor formula below.

Divisors, factorials and binomial coefficients modulo p

If n = p₁^a₁ · p₂^a₂ ··· p_k^a_k, then number of divisors d(n) = Π(aᵢ + 1) and sum of divisors σ(n) = Π (pᵢ^aᵢ+1 − 1)/(pᵢ − 1).
Divisors come in pairs (e, n/e), so enumerate them in O(√n); a perfect square has an odd number of divisors (the middle divisor is unpaired).
Total number of divisors of 1…n = Σ_{d(i)} = Σ floor(n/i) — the classic divisor-count trick, evaluated in O(√n) by grouping equal quotients. (The *sum* of those divisors is Σ i·floor(n/i).)
Legendre's formula: the exponent of prime p in n! is Σ floor(n/pⁱ). Trailing zeros of n! = exponent of 5.
nCr mod prime p (p > n): precompute fact[] and invfact[]; C(n, r) = fact[n]·invfact[r]·invfact[n−r] mod p. O(n) preprocessing, O(1) per query.
Lucas's theorem: for small prime p, C(n, r) mod p = Π C(nᵢ, rᵢ) mod p over the base-p digits; it is 0 if any digit rᵢ > nᵢ. Needed when n ≥ p.
Composite modulus: use CRT over prime-power factors (generalised Lucas / Andrew Granville's method) — rarely asked, but know that the naive inverse fails because gcd(r!, m) may exceed 1.
Pascal's rule C(n, r) = C(n−1, r) + C(n−1, r−1) builds a table in O(n²) with no inverses — fine for n ≤ 2000.

Congruence systems, Diophantine equations and discrete logarithm

Linear Diophantine equation ax + by = c is solvable iff gcd(a, b) | c. One solution comes from extended Euclid scaled by c/g; the general family is x = x₀ + (b/g)t, y = y₀ − (a/g)t.
Chinese Remainder Theorem (CRT): for pairwise coprime m₁…m_k, the system x ≡ aᵢ (mod mᵢ) has a unique solution modulo M = Πmᵢ, namely x = Σ aᵢ·Mᵢ·yᵢ mod M where Mᵢ = M/mᵢ and yᵢ = Mᵢ⁻¹ mod mᵢ.
Non-coprime CRT: merge two congruences pairwise; x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂) is solvable iff gcd(m₁, m₂) | (a₂ − a₁), and the merged modulus is lcm(m₁, m₂).
Use of CRT in code: compute a big answer modulo two or three different primes and reconstruct it — standard in NTT-based multiplication and in hash-collision-resistant hashing.
Discrete logarithm: solve a^x ≡ b (mod m). Baby-step giant-step does it in O(√m log m) time and O(√m) memory by writing x = i·⌈√m⌉ − j. No efficient general algorithm is known — that hardness is what secures Diffie-Hellman and ECC.
Primitive root + discrete log turn multiplication modulo p into addition, which is how index tables and some NTT constructions are built.

Multiplicative functions, Möbius and applied number theory

A function f is multiplicative if f(ab) = f(a)f(b) for coprime a, b — true of φ, μ, d and σ, so each can be tabulated with a linear sieve.
Möbius function: μ(1) = 1; μ(n) = (−1)^k if n is a product of k distinct primes; μ(n) = 0 if n has a squared prime factor. Σ_{d|n} μ(d) = 1 if n = 1 else 0.
Möbius inversion / inclusion-exclusion: the count of pairs (i, j) ≤ n with gcd = 1 is Σ μ(d)·floor(n/d)²; counts of "divisible by at least one of p₁…p_k" follow the same alternating pattern.
Mertens/divisor sums with the floor-grouping trick give O(√n) answers to "sum of gcds", "count of coprime pairs" style problems.
RSA: pick primes p, q; n = pq; choose e coprime to φ(n) = (p−1)(q−1); d = e⁻¹ mod φ(n); encrypt c = m^e mod n, decrypt m = c^d mod n. Security rests on the hardness of factoring n. In India, digital signatures using such schemes are legally recognised under the Information Technology Act, 2000 (Sections 3 and 3A), with Certifying Authorities licensed by the Controller of Certifying Authorities (CCA); e-Sign and DSC tokens used for GST, MCA and income-tax filings run on RSA/ECC.
Check digits are modular arithmetic in production: Aadhaar (UIDAI) appends a Verhoeff check digit computed over the dihedral group D₅, which catches all single-digit and adjacent-transposition errors that a plain mod-10 sum would miss; the 15th character of a GSTIN is a weighted base-36 checksum; ISBN-13 and the Luhn algorithm on card numbers are mod-10 schemes.
Hashing: polynomial rolling hashes, Rabin-Karp and hash maps all use a large prime modulus; choosing a random base modulo a prime is what makes anti-hash tests fail.

Key points

Euclid's algorithm - gcd(a, b) = gcd(b, a mod b), O(log min(a, b)), worst case consecutive Fibonacci numbers.
Bézout's identity - ax + by = gcd(a, b) always has an integer solution; extended Euclid finds it.
GCD-LCM identity - gcd(a, b) × lcm(a, b) = a × b, for positive a, b only.
Inverse existence - a⁻¹ mod m exists iff gcd(a, m) = 1; for prime p use a^p−2 mod p.
Fermat's little theorem - a^p−1 ≡ 1 (mod p) for prime p, p ∤ a; basis of inverses and the Fermat primality test.
Euler's totient - φ(n) = n·Π(1 − 1/p); multiplicative; φ(p) = p − 1; φ(p^k) = p^k − p^k−1.
Euler's theorem - a^φ(n) ≡ 1 (mod n) when gcd(a, n) = 1; used to reduce astronomically large exponents.
Binary exponentiation - aⁿ mod m in O(log n); never loop n times.
Sieve of Eratosthenes - all primes up to n in O(n log log n); start marking at p².
Linear sieve / SPF - O(n) table giving instant factorisation and φ, μ, d, σ for every n ≤ limit.
Segmented sieve - primes in [L, R] for R up to ~10¹² using primes up to √R.
Miller-Rabin - deterministic for all 64-bit integers with the 12 fixed prime bases; Carmichael numbers defeat the plain Fermat test.
Pollard's rho - factorise in ~O(n^1/4); pair it with Miller-Rabin.
Divisor formulas - d(n) = Π(aᵢ+1), σ(n) = Π (p^a+1 − 1)/(p − 1); enumerate divisors in O(√n).
Legendre's formula - exponent of p in n! = Σ floor(n/pⁱ); trailing zeros of n! come from the power of 5.
nCr mod p - factorials + inverse factorials for p > n; Lucas's theorem when n ≥ p (small prime).
CRT - unique x mod Πmᵢ for pairwise coprime moduli; non-coprime version needs gcd(mᵢ, mⱼ) | (aᵢ − aⱼ).
Möbius function - μ drives inclusion-exclusion over divisors: coprime-pair counts, squarefree counts, gcd sums.

Formulas and examples

a = bq + r, 0 ≤ r < b (division algorithm; a, b, q, r integers, b > 0)
gcd(a, b) = gcd(b, a mod b); gcd(a, 0) = a
a·x + b·y = gcd(a, b) (Bézout; x, y from extended Euclid)
lcm(a, b) = a·b / gcd(a, b)
aⁿ mod m by binary exponentiation: aⁿ = (a^n/2)² if n even, a·aⁿ⁻¹ if n odd
a^p−1 ≡ 1 (mod p); a⁻¹ ≡ a^p−2 (mod p) [p prime, p ∤ a]
φ(n) = n·Π_{p|n} (1 − 1/p); a^φ(n) ≡ 1 (mod n) for gcd(a, n) = 1
d(n) = Π (aᵢ + 1); σ(n) = Π (pᵢ^aᵢ+1 − 1)/(pᵢ − 1) [n = Π pᵢ^aᵢ]
v_p(n!) = Σ_{i≥1} floor(n / pⁱ) (Legendre)
C(n, r) mod p = n! · (r!)⁻¹ · ((n−r)!)⁻¹ mod p
x = Σ aᵢ·Mᵢ·(Mᵢ⁻¹ mod mᵢ) mod M, M = Πmᵢ, Mᵢ = M/mᵢ (CRT)
Σ_{i=1}^{n} floor(n/i) = total number of divisors of 1…n
Number of coprime pairs (i, j), 1 ≤ i, j ≤ n = Σ_{d=1}^{n} μ(d)·floor(n/d)²

Example 1 - extended Euclid, inverse and a Diophantine equation (a = 240, b = 46).

240 = 5·46 + 10; 46 = 4·10 + 6; 10 = 1·6 + 4; 6 = 1·4 + 2; 4 = 2·2 + 0 → gcd = 2.
Back-substitute: 2 = 6 − 4 = 2·6 − 10 = 2·46 − 9·10 = 47·46 − 9·240. Check: 2162 − 2160 = 2 ✓.
lcm(240, 46) = 240·46/2 = 11040/2 = 5520.
Solve 240x + 46y = 6: since 2 | 6, scale by 3 → x₀ = −27, y₀ = 141 (check −6480 + 6486 = 6 ✓). General solution x = −27 + 23t, y = 141 − 120t.

Example 2 - modular exponentiation and inverse.

3¹³ mod 17 by squaring: 3¹ = 3, 3² = 9, 3⁴ = 81 mod 17 = 13, 3⁸ = 13² = 169 mod 17 = 16. Since 13 = 8 + 4 + 1: 16·13 = 208 mod 17 = 4; 4·3 = 12.
Inverse of 10 mod 17 = 10¹⁵ mod 17, or by inspection 10·12 = 120 = 7·17 + 1 → 12.
7²²² mod 11: Fermat gives 7¹⁰ ≡ 1, and 222 mod 10 = 2, so the answer is 7² = 49 mod 11 = 5.
Inverse of 3 modulo 10⁹+7 = (10⁹+8)/3 = 333333336 (3 × 333333336 = 1000000008 ≡ 1) ✓.

Example 3 - totient and divisors of 360 = 2³·3²·5.

φ(360) = 360·(1/2)·(2/3)·(4/5) = 360·8/30 = 96.
d(360) = (3+1)(2+1)(1+1) = 24 divisors.
σ(360) = (2⁴−1)/1 · (3³−1)/2 · (5²−1)/4 = 15 · 13 · 6 = 1170.

Example 4 - CRT and nCr mod p.

Solve x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7). M = 105; M₁ = 35, 35⁻¹ mod 3 = 2; M₂ = 21, 21⁻¹ mod 5 = 1; M₃ = 15, 15⁻¹ mod 7 = 1. x = 2·35·2 + 3·21·1 + 2·15·1 = 140 + 63 + 30 = 233 → 233 mod 105 = 23. Check: 23 mod 3 = 2, mod 5 = 3, mod 7 = 2 ✓.
C(10, 3) mod 13: numerator 10·9·8 = 720 ≡ 720 − 715 = 5; denominator 3! = 6, and 6·11 = 66 ≡ 1 so 6⁻¹ = 11; answer 5·11 = 55 mod 13 = 3 (and indeed C(10,3) = 120 = 9·13 + 3 ✓).

Example 5 - Legendre, inclusion-exclusion and a real check digit.

Trailing zeros in 100! = floor(100/5) + floor(100/25) = 20 + 4 = 24.
Integers in 1…100 divisible by 2, 3 or 5 = (50 + 33 + 20) − (16 + 10 + 6) + 3 = 74, so 26 are coprime to 30.
ISBN-13 check digit for 978-0-306-40615-?: weighted sum (weights 1,3,1,3,…) = 9+21+8+0+3+0+6+12+0+18+1+15 = 93; check digit = (10 − 93 mod 10) mod 10 = 7.

Task	Naive	Efficient	Complexity
GCD	subtract repeatedly	Euclid	O(log min(a,b))
aⁿ mod m	n multiplications	binary exponentiation	O(log n)
Primality of n	divide by all < n	trial division to √n / Miller-Rabin	O(√n) / O(k log³n)
Primes ≤ n	test each	Eratosthenes / linear sieve	O(n log log n) / O(n)
Factorise n	trial division	Pollard's rho + Miller-Rabin	O(n^1/4)
Many C(n,r) mod p	Pascal table	factorial + inverse factorial	O(n) then O(1)
Inverse mod m	brute force 1…m	extended Euclid / a^p−2	O(log m)

long long modpow(long long a, long long n, long long m){
    long long r = 1; a %= m;
    while(n > 0){ if(n & 1) r = r * a % m; a = a * a % m; n >>= 1; }
    return r;                       // a,m < 1e9 keeps products < 1e18
}
long long gcd(long long a,long long b){ return b ? gcd(b, a % b) : a; }
// sieve + smallest prime factor
vector<int> spf(N+1);
for(int i=2;i<=N;i++) if(!spf[i]) for(long long j=i;j<=N;j+=i) if(!spf[j]) spf[j]=i;

Where it is used

Cryptography and fintech: RSA/ECC key generation and signing in UPI, NPCI and bank payment gateways, Aadhaar e-KYC, DSC tokens for GST/MCA/ITR filings under the IT Act, 2000; roles such as security engineer and payments backend developer at Razorpay, PhonePe, Paytm and HDFC/ICICI tech teams.
Identity and document validation: Verhoeff check digit in Aadhaar numbers (UIDAI), the mod-36 checksum character in GSTIN, Luhn validation of card numbers, ISBN/IFSC/UPI VPA format checks — implemented in every onboarding and KYC form.
Competitive programming and hiring tests: TCS CodeVita, Infosys HackWithInfy, Amazon/Microsoft/Google online rounds and Codeforces/CodeChef routinely require answers modulo 10⁹+7, combinatorics with inverse factorials, or sieves over 10⁶–10^7.
Hashing, databases and distributed systems: polynomial string hashing, Bloom filters, consistent hashing rings and shard keys all use large primes and modular reduction.
Signal processing and big-number arithmetic: number-theoretic transform (NTT) modulo 998244353 for exact polynomial and big-integer multiplication, used in cryptographic libraries and in lattice-based post-quantum schemes.
Error detection and embedded systems: CRC and parity schemes, random-number generators (linear congruential, x → ax + c mod m), and clock/scheduler problems solved with LCM — common in ISRO, DRDO and semiconductor firmware interviews.

Interview questions

Q: Why does the Euclidean algorithm terminate quickly? A: Each step replaces (a, b) with (b, a mod b) and the remainder shrinks at least geometrically; the worst case is consecutive Fibonacci numbers, giving about 1.44·log₂ n steps.
Q: When does a modular inverse of a exist mod m, and how do you compute it? A: Exactly when gcd(a, m) = 1; compute it with extended Euclid, or as a^p−2 mod p by Fermat if m = p is prime.
Q: Why is 10⁹+7 used as the modulus? A: It is prime (so all non-zero inverses exist) and small enough that the product of two residues stays under 2⁶³, so 64-bit arithmetic does not overflow.
Q: Compute 2¹⁰⁰ mod 1000000007 conceptually. A: Binary exponentiation — 100 = 1100100₂, so about 6 squarings plus 2 extra multiplications, roughly 8 in all instead of 100: an O(log n) algorithm.
Q: How do you find all primes up to 10⁷ and the primes between 10¹² and 10¹² + 10⁶? A: Eratosthenes with a bitset for the first; a segmented sieve using primes up to 10⁶ to mark the window for the second.
Q: Is the Fermat primality test reliable? A: No — Carmichael numbers such as 561 and 1729 pass for every coprime base; Miller-Rabin with the fixed bases up to 37 is deterministic for all 64-bit integers.
Q: How many divisors does 1,000,000 have? A: 10⁶ = 2⁶·5⁶, so (6+1)(6+1) = 49 divisors.
Q: How do you compute C(10⁶, 500000) mod 10⁹+7? A: Precompute factorials and inverse factorials up to 10⁶ in O(n), then one multiplication of three terms; Lucas is not needed since the modulus exceeds n.
Q: What does the Chinese Remainder Theorem give you in code? A: A unique residue modulo the product of pairwise-coprime moduli, letting you compute an answer under several small primes and reconstruct the true value — used in NTT and multi-modulus hashing.
Q: How would you compute a^b mod m when b has 10⁵ digits? A: Reduce b modulo φ(m) by Euler's theorem (processing the digit string), using the generalised exponent φ(m) + b mod φ(m) if gcd(a, m) ≠ 1.
Q: Why does a perfect square have an odd number of divisors? A: Divisors pair as (e, n/e); only for a square does one divisor pair with itself (√n), leaving the count odd.
Q: Why does Aadhaar not use a simple mod-10 digit sum? A: A plain weighted sum misses transposition of adjacent digits; the Verhoeff scheme over the dihedral group D₅ detects all single-digit errors and all adjacent transpositions.

Common mistakes

Forgetting to normalise negative remainders — (a - b) % m can be negative in C++/Java; use ((a - b) % m + m) % m.
Overflow: multiplying two residues near 10⁹ in int, or near 10¹⁸ in long long without __int128.
Dividing under a modulus (x / y % m) instead of multiplying by the inverse of y, or taking an inverse when gcd(y, m) ≠ 1.
Using a * b / gcd(a, b) for LCM and overflowing before the division — divide first.
Starting sieve marking at 2p instead of p², mis-sizing the array by one, or treating 1 as prime.
Applying the factorial-inverse nCr formula when n ≥ p (needs Lucas) or when the modulus is composite.
Using a loop for aⁿ or trial division beyond √n, then blaming the judge for TLE; and assuming "random base Fermat" is a proof of primality.