Chapter 12 of 30

Basic Number Theory & Modular Arithmetic

Master divisibility, GCD/LCM, primes, sieve, modular arithmetic, and binary exponentiation for competitive programming.

DivisibilityGCD & LCMPrimes & Primality TestingSieve of EratosthenesPrime FactorizationDivisor EnumerationModular ArithmeticBinary ExponentiationParity ArgumentsSum Formulas

Basic Number Theory & Modular Arithmetic

Number theory is everywhere in competitive programming. Modular arithmetic keeps numbers manageable, GCD/LCM are fundamental tools, and understanding primes unlocks many problem categories.

Divisibility

An integer a is divisible by b if a % b == 0.

hljs cpp

bool divisible = (a % b == 0);

Divisibility Rules

Divisible by 2: last digit is even
Divisible by 3: digit sum is divisible by 3
Divisible by 4: last two digits form a number divisible by 4
Divisible by 5: last digit is 0 or 5
Divisible by 9: digit sum is divisible by 9

GCD & LCM

GCD (Greatest Common Divisor)

The largest number that divides both a and b:

hljs cpp

// Using __gcd (built-in)
int g = __gcd(a, b);

// Using std::gcd (C++17)
int g = gcd(a, b);

// Euclidean algorithm (for understanding)
int gcd(int a, int b) {
    while (b) { int t = b; b = a % b; a = t; }
    return a;
}

LCM (Least Common Multiple)

The smallest number divisible by both a and b:

hljs cpp

// Always compute as (a / gcd(a,b)) * b to avoid overflow
long long lcm(int a, int b) {
    return (long long)a / __gcd(a, b) * b;
}

GCD Properties

gcd(a, 0) = a
gcd(a, b) = gcd(b, a % b)
gcd(a, b, c) = gcd(gcd(a, b), c)
lcm(a, b) = a * b / gcd(a, b)

Primes & Primality Testing

A prime number has exactly two divisors: 1 and itself.

hljs cpp

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

This runs in O(√n) — fast enough for numbers up to ~10¹².

Sieve of Eratosthenes

Find all primes up to N in O(N log log N):

hljs cpp

const int MAX = 1000001;
bool is_prime[MAX];

void sieve() {
    fill(is_prime, is_prime + MAX, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < MAX; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAX; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

Segmented Sieve

For primes up to 10⁹ (but only up to √N for the sieve):

hljs cpp

// Sieve primes up to sqrt(10^9) ≈ 31623
// Then use them to sieve ranges

Prime Factorization

hljs cpp

vector<pair<int,int>> factorize(int n) {
    vector<pair<int,int>> factors;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            factors.push_back({i, cnt});
        }
    }
    if (n > 1) factors.push_back({n, 1});
    return factors;
}

Precomputed Smallest Prime Factor (SPF)

hljs cpp

const int MAX = 1000001;
int spf[MAX];

void buildSPF() {
    for (int i = 2; i < MAX; i++) spf[i] = i;
    for (int i = 2; i * i < MAX; i++) {
        if (spf[i] == i) {
            for (int j = i * i; j < MAX; j += i) {
                if (spf[j] == j) spf[j] = i;
            }
        }
    }
}

// Factorize in O(log n) using SPF
vector<int> factorize(int n) {
    vector<int> factors;
    while (n > 1) {
        factors.push_back(spf[n]);
        n /= spf[n];
    }
    return factors;
}

Divisor Enumeration

hljs cpp

vector<int> getDivisors(int n) {
    vector<int> divisors;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divisors.push_back(i);
            if (i != n / i) divisors.push_back(n / i);
        }
    }
    return divisors;
}

Number of divisors: if n = p1^a1 * p2^a2 * ..., then d(n) = (a1+1)(a2+1)...

Modular Arithmetic

Basic Rules

code

(a + b) % m = ((a % m) + (b % m)) % m
(a * b) % m = ((a % m) * (b % m)) % m
(a - b + m) % m  // adding m prevents negative

Modular Addition (Safe)

hljs cpp

const int MOD = 1e9 + 7;

int add(int a, int b) {
    return (a + b) % MOD;
}

int sub(int a, int b) {
    return (a - b + MOD) % MOD;
}

int mul(int a, int b) {
    return (1LL * a * b) % MOD;
}

Modular Inverse

The number x such that (a * x) % m == 1:

hljs cpp

// When MOD is prime (Fermat's Little Theorem)
int power(int base, int exp, int mod);

int modInverse(int a) {
    return power(a, MOD - 2, MOD);
}

Binary Exponentiation

Compute a^n in O(log n):

hljs cpp

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

Why O(log n)?

Each iteration halves exp:

exp = 16 → 8 → 4 → 2 → 1 (4 steps)
exp = 1000000 → about 20 steps

Parity Arguments

Even ± Even = Even
Odd ± Odd = Even
Even ± Odd = Odd
Even × Anything = Even
Odd × Odd = Odd

Sum Formulas

code

1 + 2 + ... + n = n(n+1)/2
1² + 2² + ... + n² = n(n+1)(2n+1)/6
1³ + 2³ + ... + n³ = (n(n+1)/2)²

Summary

__gcd(a, b) for GCD; a / __gcd(a, b) * b for LCM (avoids overflow)
Sieve of Eratosthenes: O(N log log N) for all primes up to N
Modular multiplication: always use 1LL * a * b % MOD
Binary exponentiation: O(log n) for a^n % MOD
Modular inverse: modInverse(a) = power(a, MOD-2, MOD) when MOD is prime

Ch 11: Complexity & Problem Solving Ch 13: Prefix Sums & Difference Arrays

Prefer reading offline? Download the full book as a PDF.

Download Free Book

Chapter 12 of 30

Basic Number Theory & Modular Arithmetic

Master divisibility, GCD/LCM, primes, sieve, modular arithmetic, and binary exponentiation for competitive programming.

DivisibilityGCD & LCMPrimes & Primality TestingSieve of EratosthenesPrime FactorizationDivisor EnumerationModular ArithmeticBinary ExponentiationParity ArgumentsSum Formulas

Basic Number Theory & Modular Arithmetic

Number theory is everywhere in competitive programming. Modular arithmetic keeps numbers manageable, GCD/LCM are fundamental tools, and understanding primes unlocks many problem categories.

Divisibility

An integer a is divisible by b if a % b == 0.

hljs cpp

bool divisible = (a % b == 0);

Divisibility Rules

Divisible by 2: last digit is even
Divisible by 3: digit sum is divisible by 3
Divisible by 4: last two digits form a number divisible by 4
Divisible by 5: last digit is 0 or 5
Divisible by 9: digit sum is divisible by 9

GCD & LCM

GCD (Greatest Common Divisor)

The largest number that divides both a and b:

hljs cpp

// Using __gcd (built-in)
int g = __gcd(a, b);

// Using std::gcd (C++17)
int g = gcd(a, b);

// Euclidean algorithm (for understanding)
int gcd(int a, int b) {
    while (b) { int t = b; b = a % b; a = t; }
    return a;
}

LCM (Least Common Multiple)

The smallest number divisible by both a and b:

hljs cpp

// Always compute as (a / gcd(a,b)) * b to avoid overflow
long long lcm(int a, int b) {
    return (long long)a / __gcd(a, b) * b;
}

GCD Properties

gcd(a, 0) = a
gcd(a, b) = gcd(b, a % b)
gcd(a, b, c) = gcd(gcd(a, b), c)
lcm(a, b) = a * b / gcd(a, b)

Primes & Primality Testing

A prime number has exactly two divisors: 1 and itself.

hljs cpp

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

This runs in O(√n) — fast enough for numbers up to ~10¹².

Sieve of Eratosthenes

Find all primes up to N in O(N log log N):

hljs cpp

const int MAX = 1000001;
bool is_prime[MAX];

void sieve() {
    fill(is_prime, is_prime + MAX, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < MAX; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAX; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

Segmented Sieve

For primes up to 10⁹ (but only up to √N for the sieve):

hljs cpp

// Sieve primes up to sqrt(10^9) ≈ 31623
// Then use them to sieve ranges

Prime Factorization

hljs cpp

vector<pair<int,int>> factorize(int n) {
    vector<pair<int,int>> factors;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            factors.push_back({i, cnt});
        }
    }
    if (n > 1) factors.push_back({n, 1});
    return factors;
}

Precomputed Smallest Prime Factor (SPF)

hljs cpp

const int MAX = 1000001;
int spf[MAX];

void buildSPF() {
    for (int i = 2; i < MAX; i++) spf[i] = i;
    for (int i = 2; i * i < MAX; i++) {
        if (spf[i] == i) {
            for (int j = i * i; j < MAX; j += i) {
                if (spf[j] == j) spf[j] = i;
            }
        }
    }
}

// Factorize in O(log n) using SPF
vector<int> factorize(int n) {
    vector<int> factors;
    while (n > 1) {
        factors.push_back(spf[n]);
        n /= spf[n];
    }
    return factors;
}

Divisor Enumeration

hljs cpp

vector<int> getDivisors(int n) {
    vector<int> divisors;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divisors.push_back(i);
            if (i != n / i) divisors.push_back(n / i);
        }
    }
    return divisors;
}

Number of divisors: if n = p1^a1 * p2^a2 * ..., then d(n) = (a1+1)(a2+1)...

Modular Arithmetic

Basic Rules

code

(a + b) % m = ((a % m) + (b % m)) % m
(a * b) % m = ((a % m) * (b % m)) % m
(a - b + m) % m  // adding m prevents negative

Modular Addition (Safe)

hljs cpp

const int MOD = 1e9 + 7;

int add(int a, int b) {
    return (a + b) % MOD;
}

int sub(int a, int b) {
    return (a - b + MOD) % MOD;
}

int mul(int a, int b) {
    return (1LL * a * b) % MOD;
}

Modular Inverse

The number x such that (a * x) % m == 1:

hljs cpp

// When MOD is prime (Fermat's Little Theorem)
int power(int base, int exp, int mod);

int modInverse(int a) {
    return power(a, MOD - 2, MOD);
}

Binary Exponentiation

Compute a^n in O(log n):

hljs cpp

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

Why O(log n)?

Each iteration halves exp:

exp = 16 → 8 → 4 → 2 → 1 (4 steps)
exp = 1000000 → about 20 steps

Parity Arguments

Even ± Even = Even
Odd ± Odd = Even
Even ± Odd = Odd
Even × Anything = Even
Odd × Odd = Odd

Sum Formulas

code

1 + 2 + ... + n = n(n+1)/2
1² + 2² + ... + n² = n(n+1)(2n+1)/6
1³ + 2³ + ... + n³ = (n(n+1)/2)²

Summary

__gcd(a, b) for GCD; a / __gcd(a, b) * b for LCM (avoids overflow)
Sieve of Eratosthenes: O(N log log N) for all primes up to N
Modular multiplication: always use 1LL * a * b % MOD
Binary exponentiation: O(log n) for a^n % MOD
Modular inverse: modInverse(a) = power(a, MOD-2, MOD) when MOD is prime

Ch 11: Complexity & Problem Solving Ch 13: Prefix Sums & Difference Arrays

Prefer reading offline? Download the full book as a PDF.

Download Free Book