Back to Study Material Data Structures and Algorithms

Number Theory for DSA

Number theory provides the mathematical backbone for a substantial portion of competitive programming problems and technical interview questions involving ...

Number Theory for DSA

Foundational Number Theory Concepts Every DSA Practitioner Needs

Number theory provides the mathematical backbone for a substantial portion of competitive programming problems and technical interview questions involving arithmetic, cryptography, and combinatorics. The most important building block is the concept of divisibility and prime factorization. Every integer greater than one can be expressed uniquely as a product of prime powers — this is the Fundamental Theorem of Arithmetic, and it underpins algorithms for computing GCD, LCM, and Euler's totient function.

The greatest common divisor of two integers a and b is the largest integer that divides both. The Euclidean algorithm computes GCD(a, b) by repeatedly replacing (a, b) with (b, a mod b) until b reaches zero, at which point a holds the GCD. This runs in O(log(min(a, b))) time. The extended Euclidean algorithm additionally computes integers x and y such that ax + by = GCD(a, b), which is essential for finding modular inverses when the modulus is not prime.

Euler's totient function phi(n) counts the number of integers from 1 to n that are coprime to n. For a prime p, phi(p) = p - 1. For a prime power p^k, phi(p^k) = p^(k-1) * (p - 1). The function is multiplicative, so for n = p1^a1 * p2^a2 * ..., phi(n) = n * product of (1 - 1/p) over all prime factors p. This function appears in Euler's theorem and RSA-style problems in competitive programming.

Prime Factorization, Divisors, and Multiplicative Functions

Trial division factorizes n by testing all primes up to sqrt(n), running in O(sqrt(n)) time. After dividing out all small primes, if the remaining value exceeds 1, it is itself prime. For large n, Pollard's rho algorithm factorizes in expected O(n^(1/4)) time using a probabilistic cycle-finding approach, making it practical for n up to 10^18 in competitive settings.

The number of divisors d(n) and their sum sigma(n) are multiplicative functions computable from the prime factorization. If n = p1^a1 * p2^a2 * ..., then d(n) = product of (ai + 1) and sigma(n) = product of (p^(ai+1) - 1)/(p - 1). These formulas let you answer divisor-counting queries directly without enumerating all divisors, which becomes critical when n can be as large as 10^12.

The sieve of smallest prime factors (SPF sieve) precomputes the smallest prime factor of every number up to N in O(N log log N) time. Once the SPF array is built, factorizing any number up to N takes O(log n) time by repeatedly dividing by its smallest prime factor. This technique is invaluable when you need to factorize many numbers quickly — for example, answering Q offline queries about divisor counts, where Q can be up to 10^6.

Modular Inverses, Chinese Remainder Theorem, and Practical Applications

The modular inverse of a modulo m is an integer x such that ax ≡ 1 (mod m). It exists if and only if GCD(a, m) = 1. When m is prime, Fermat's little theorem gives a^(-1) ≡ a^(m-2) (mod m), computable in O(log m) via fast exponentiation. When m is not prime, use the extended Euclidean algorithm instead.

The Chinese Remainder Theorem (CRT) states that if m1, m2, ..., mk are pairwise coprime moduli, then for any choice of remainders r1, r2, ..., rk there exists a unique solution x modulo M = m1 * m2 * ... * mk satisfying x ≡ ri (mod mi) for all i. CRT appears in problems that require combining information from multiple modular constraints, and its constructive proof directly yields an algorithm for finding x.

A concrete application: suppose you need to compute C(n, k) mod p for large n and k where p is a large prime. You precompute factorial and inverse factorial arrays modulo p, then answer each query in O(1) using C(n, k) = n! * inv(k!) * inv((n-k)!) mod p. When p is not prime or is small, Lucas's theorem or Granville's generalization handles the computation correctly. These combinatorial computations appear constantly in counting problems and probability questions in both interviews and contests.