Basic Math

Prime numbers, GCD, LCM, modular arithmetic, and combinatorics

Master fundamental mathematical concepts essential for algorithmic problem solving. This article covers core algorithms and techniques used in competitive programming, cryptography, system design, and number theory applications.

Prime Numbers

Prime Number Properties

• Definition: Natural number greater than 1 with no positive divisors other than 1 and itself
• First few primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47...
• Importance: Primes are fundamental in cryptography, hashing, and algorithm design
• Distribution: Approximately n/ln(n) primes less than n (Prime Number Theorem)
• Properties: All primes > 3 are of form 6k±1 (used in optimized checking)

Prime Checking

Trial Division (Optimized)

// Check if a number is prime (O(√n))
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    // All primes > 3 are of form 6k±1
    // Check divisibility by numbers of this form up to √n
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

// Time complexity: O(√n)
// Space complexity: O(1)
// Fast enough for n up to ~10^9

Sieve of Eratosthenes

// Generate all primes up to n
vector<bool> sieve(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime;
}

Prime Factorization

// Get prime factors of a number
vector<pair<int, int>> primeFactors(int n) {
    vector<pair<int, int>> factors;
    
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int count = 0;
            while (n % i == 0) {
                n /= i;
                count++;
            }
            factors.push_back({i, count});
        }
    }
    
    if (n > 1) {
        factors.push_back({n, 1});
    }
    
    return factors;
}

GCD & LCM

Greatest Common Divisor (GCD)

// Euclidean algorithm
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Recursive version
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

Least Common Multiple (LCM)

// LCM using GCD
int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;
}

Extended Euclidean Algorithm

// Find x, y such that ax + by = gcd(a, b)
int extendedGcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    
    int x1, y1;
    int g = extendedGcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

Modular Arithmetic

Modular Addition

// (a + b) mod m
int modAdd(int a, int b, int m) {
    return ((a % m) + (b % m)) % m;
}

Modular Multiplication

// (a * b) mod m
int modMul(int a, int b, int m) {
    return ((a % m) * (b % m)) % m;
}

Modular Exponentiation

// (a^b) mod m
int modPow(int base, int exp, int mod) {
    int result = 1;
    base %= mod;
    
    while (exp > 0) {
        if (exp & 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp >>= 1;
    }
    
    return result;
}

Modular Inverse

// Find x such that (a * x) ≡ 1 (mod m)
int modInverse(int a, int m) {
    int x, y;
    int g = extendedGcd(a, m, x, y);
    
    if (g != 1) {
        return -1; // No inverse exists
    }
    
    return (x % m + m) % m;
}

Factorial & Permutations

Factorial

// Calculate n!
long long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

// Factorial with modulo
int factorialMod(int n, int mod) {
    long long result = 1;
    for (int i = 2; i <= n; i++) {
        result = (result * i) % mod;
    }
    return result;
}

Permutations

// Calculate P(n, r) = n! / (n-r)!
long long permutation(int n, int r) {
    if (r > n) return 0;
    
    long long result = 1;
    for (int i = 0; i < r; i++) {
        result *= (n - i);
    }
    return result;
}

Combinations

// Calculate C(n, r) = n! / (r! * (n-r)!)
long long combination(int n, int r) {
    if (r > n) return 0;
    if (r > n - r) r = n - r; // Optimization
    
    long long result = 1;
    for (int i = 0; i < r; i++) {
        result = result * (n - i) / (i + 1);
    }
    return result;
}

Combinatorics

Pascal's Triangle

// Generate Pascal's triangle
vector<vector<int>> pascalTriangle(int n) {
    vector<vector<int>> triangle(n);
    
    for (int i = 0; i < n; i++) {
        triangle[i].resize(i + 1);
        triangle[i][0] = triangle[i][i] = 1;
        
        for (int j = 1; j < i; j++) {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
    }
    
    return triangle;
}

Catalan Numbers

// Calculate nth Catalan number
long long catalan(int n) {
    if (n <= 1) return 1;
    
    long long result = 0;
    for (int i = 0; i < n; i++) {
        result += catalan(i) * catalan(n - 1 - i);
    }
    return result;
}

// Dynamic programming approach
long long catalanDP(int n) {
    vector<long long> dp(n + 1, 0);
    dp[0] = dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] += dp[j] * dp[i - 1 - j];
        }
    }
    
    return dp[n];
}

Fibonacci Numbers

// Calculate nth Fibonacci number
long long fibonacci(int n) {
    if (n <= 1) return n;
    
    long long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long long temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

Number Theory Concepts

Divisors

// Get all divisors of a number
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);
            }
        }
    }
    
    sort(divisors.begin(), divisors.end());
    return divisors;
}

Totient Function (Euler's Phi)

// Calculate φ(n) - count of numbers coprime to n
int eulerPhi(int n) {
    int result = n;
    
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) {
                n /= i;
            }
            result -= result / i;
        }
    }
    
    if (n > 1) {
        result -= result / n;
    }
    
    return result;
}

Common Patterns

1. Prime factorization for divisor problems
2. GCD/LCM for fraction and multiple problems
3. Modular arithmetic for large number calculations
4. Combinatorics for counting problems
5. Number theory for mathematical properties

Advanced Topics

Chinese Remainder Theorem

Solve system of congruences:

// Find x such that:
// x ≡ a1 (mod m1)
// x ≡ a2 (mod m2)
// ...
// x ≡ ak (mod mk)

long long crt(vector<long long> a, vector<long long> m) {
    long long M = 1;
    for (auto mi : m) M *= mi;

    long long x = 0;
    for (int i = 0; i < a.size(); i++) {
        long long Mi = M / m[i];
        long long yi = modInverse(Mi, m[i]);
        x += a[i] * Mi * yi;
        x %= M;
    }
    return x;
}

Binary Exponentiation

Compute large powers efficiently:

// Compute a^b mod m in O(log b) time
long long binaryExp(long long a, long long b, long long m) {
    long long result = 1;
    a %= m;

    while (b > 0) {
        if (b & 1) result = (result * a) % m;  // b is odd
        a = (a * a) % m;
        b >>= 1;
    }
    return result;
}

// Example: compute 2^1000000 mod 10^9+7
long long answer = binaryExp(2, 1000000, 1000000007);

Miller-Rabin Primality Test

Fast probabilistic primality testing for large numbers:

// Deterministic for n < 3,317,044,064,679,887,385,961,981
bool millerRabin(long long n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;

    // Write n-1 as 2^r * d
    long long d = n - 1;
    int r = 0;
    while (d % 2 == 0) {
        d /= 2;
        r++;
    }

    // Test with several bases
    vector<long long> bases = {2, 3, 5, 7, 11, 13, 17, 19, 23};
    for (long long a : bases) {
        if (a >= n) continue;

        long long x = modPow(a, d, n);
        if (x == 1 || x == n - 1) continue;

        bool composite = true;
        for (int i = 0; i < r - 1; i++) {
            x = (x * x) % n;
            if (x == n - 1) {
                composite = false;
                break;
            }
        }

        if (composite) return false;
    }

    return true;
}

Real-World Applications

Cryptography

// RSA Public Key Cryptography
// Public key: (e, n)
// Private key: (d, n)

// Encryption: C = M^e mod n
long long encrypt(long long message, long long e, long long n) {
    return modPow(message, e, n);
}

// Decryption: M = C^d mod n
long long decrypt(long long ciphertext, long long d, long long n) {
    return modPow(ciphertext, d, n);
}

// Key generation requires:
// 1. Choose two large primes p, q
// 2. Compute n = p * q
// 3. Compute φ(n) = (p-1)(q-1)
// 4. Choose e coprime to φ(n)
// 5. Find d = e^-1 mod φ(n) (modular inverse)

Number Theory in Competitive Programming

// Problem: Count pairs (a, b) where gcd(a, b) = 1 for 1 <= a, b <= n
// Solution: Use Euler's Totient function

long long countCoprimes(int n) {
    long long count = 0;
    for (int i = 1; i <= n; i++) {
        count += eulerPhi(i);
    }
    return 2 * count - 1;  // Symmetric pairs, subtract (n, n)
}

// Problem: Find modular inverse without extended GCD
// If prime modulus, use Fermat's Little Theorem: a^(p-1) ≡ 1 (mod p)
// Therefore: a^-1 ≡ a^(p-2) (mod p)

long long modInversePrime(long long a, long long p) {
    return modPow(a, p - 2, p);
}

Performance Tips

• Use sieve for multiple prime checks (first 10M primes in ~100ms)
• Precompute factorials for combination problems (store all n! up to 10^6)
• Use modular arithmetic to prevent overflow (work mod 10^9+7)
• Optimize GCD with binary GCD algorithm (faster than Euclidean)
• Cache results for expensive calculations (memoization for Catalan, Fibonacci)
• Use Miller-Rabin for primality testing of huge numbers (deterministic for reasonably small n)
• Apply CRT for system of modular equations (combines multiple constraints)

Complexity Summary

Operation	Time	Space	Notes
Prime check	O(√n)	O(1)	Trial division
Sieve (up to n)	O(n log log n)	O(n)	All primes up to n
GCD	O(log min(a,b))	O(log n) recursive	Euclidean algorithm
Prime factorization	O(√n)	O(log n)	Trial division
Modular exponentiation	O(log b)	O(log b) recursive	Binary exponentiation
Factorial	O(n)	O(1) or O(n)	Iterative or precomputed
Combination C(n,r)	O(min(r, n-r))	O(1)	Optimized
Catalan numbers	O(n) DP	O(n)	DP approach
Miller-Rabin	O(k log n)	O(log n)	k iterations for confidence