Number Theory Basics

Number Theory is one of the important topics frequently found in competitions. Many problems require knowledge of integers, divisibility, and prime numbers.

Divisibility

Integer $a$ is divisible by $b$, written as $b \mid a$, means $a = b \times k$ for some integer $k$.

// Check divisibility
bool isDivisible(int a, int b) {
    return a % b == 0;
}

Greatest Common Divisor (GCD)

GCD is the largest number that divides both numbers.

Euclidean Algorithm

// Euclidean method O(log(min(a,b)))
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Or using recursion
int gcdRecursive(int a, int b) {
    if (b == 0) return a;
    return gcdRecursive(b, a % b);
}

// C++ has __gcd and std::gcd (C++17)
#include <algorithm>
int g = __gcd(12, 18); // 6

How It Works

$\gcd(a, b) = \gcd(b, a \mod b)$

Example: Find $\gcd(48, 18)$

• $\gcd(48, 18) = \gcd(18, 48 \mod 18) = \gcd(18, 12)$
• $\gcd(18, 12) = \gcd(12, 18 \mod 12) = \gcd(12, 6)$
• $\gcd(12, 6) = \gcd(6, 12 \mod 6) = \gcd(6, 0)$
• $\gcd(6, 0) = 6$

Least Common Multiple (LCM)

LCM is the smallest number that is divisible by both numbers.

// Formula: lcm(a, b) = (a * b) / gcd(a, b)
long long lcm(long long a, long long b) {
    return a / __gcd(a, b) * b; // Divide before multiply to prevent overflow
}

// C++17 has std::lcm
#include <numeric>
long long l = std::lcm(12, 18); // 36

⚠️ Warning: Be careful of overflow when multiplying $a \times b$. Divide by gcd before multiplying.

Extended Euclidean Algorithm

Extended GCD finds values $x, y$ such that $ax + by = \gcd(a, b)$

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

Usage Example

int x, y;
int g = extGcd(35, 15, x, y);
// g = 5, x = 1, y = -2
// Verify: 35 * 1 + 15 * (-2) = 35 - 30 = 5 ✓

Factorization

Trial Division

// Find all prime factors O(sqrt(n))
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 count = 0;
            while (n % i == 0) {
                n /= i;
                count++;
            }
            factors.push_back({i, count});
        }
    }
    
    if (n > 1) {
        factors.push_back({n, 1});
    }
    
    return factors;
}

// Example: factorize(60)
// Returns: [(2, 2), (3, 1), (5, 1)]
// 60 = 2² × 3 × 5

Number of Divisors

If $n = p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k}$

Number of divisors of $n$ is $(a_1 + 1)(a_2 + 1)...(a_k + 1)$

int countDivisors(int n) {
    int count = 1;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int exp = 0;
            while (n % i == 0) {
                n /= i;
                exp++;
            }
            count *= (exp + 1);
        }
    }
    if (n > 1) count *= 2;
    return count;
}

Sum of Divisors

$\sigma(n) = \prod_{i=1}^{k} \frac{p_i^{a_i+1} - 1}{p_i - 1}$

long long sumDivisors(int n) {
    long long sum = 1;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            long long p = i;
            long long term = 1;
            while (n % i == 0) {
                n /= i;
                term = term * p + 1;
            }
            sum *= term;
        }
    }
    if (n > 1) sum *= (1 + n);
    return sum;
}

Finding All Divisors

// O(sqrt(n))
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;
}

// Example: getDivisors(12)
// Returns: [1, 2, 3, 4, 6, 12]

Euler’s Totient Function (φ)

$\phi(n)$ is the count of positive integers less than or equal to $n$ that are coprime with $n$ (gcd = 1)

Formula

$\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$

int phi(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;
}

Important Properties

• $\phi(1) = 1$
• $\phi(p) = p - 1$ for prime $p$
• $\phi(p^k) = p^{k-1}(p - 1)$
• $\phi(ab) = \phi(a)\phi(b)$ when $\gcd(a, b) = 1$

Example Problem

Problem: Count pairs (i, j) where gcd(i, j) = 1

// Given n, count pairs (i, j) where 1 ≤ i < j ≤ n and gcd(i, j) = 1
long long countCoprimePairs(int n) {
    long long count = 0;
    for (int i = 1; i <= n; i++) {
        count += phi(i);
    }
    return count - 1; // Subtract pair (1, 1)
}

Summary

Function	Formula/Method	Complexity
GCD	Euclidean	$O(\log n)$
LCM	$\frac{a \times b}{\gcd(a,b)}$	$O(\log n)$
Factorization	Trial Division	$O(\sqrt{n})$
Count Divisors	$(a_1+1)(a_2+1)...$	$O(\sqrt{n})$
Euler’s φ	$n\prod(1-\frac{1}{p})$	$O(\sqrt{n})$

💡 Tip: In C++, you can use __gcd() for GCD and std::lcm() (C++17) for LCM directly.