GCD, LCM, and Modular Arithmetic

The previous page gave you the tools to decompose numbers into primes. This page shows you what to do with that decomposition: computing GCDs and LCMs, working under a modulus, and Euler's Totient Function — the count of numbers coprime to $M$.

These aren't abstract math concepts. Modular inverse shows up every time a problem says "output the answer modulo $10^9 + 7$." GCD and LCM appear in fraction arithmetic, cycle detection, and scheduling problems. Euler's Totient connects to Fermat's theorem and is the foundation for RSA cryptography.

GCD and LCM as Set Operations

Here's the cleanest way to think about GCD and LCM: they're set operations on prime factorizations.

Write two numbers using their prime factors:

\[A = 2^3 \times 3^1 \times 5^0 = 24$$ $$B = 2^1 \times 3^2 \times 5^1 = 90\]

Now:

GCD = intersection. For each prime, take the minimum exponent.

\[\gcd(24, 90) = 2^{\min(3,1)} \times 3^{\min(1,2)} \times 5^{\min(0,1)} = 2^1 \times 3^1 \times 5^0 = 6\]

LCM = union. For each prime, take the maximum exponent.

\[\text{lcm}(24, 90) = 2^{\max(3,1)} \times 3^{\max(1,2)} \times 5^{\max(0,1)} = 2^3 \times 3^2 \times 5^1 = 360\]

This gives an elegant identity:

\[\gcd(A, B) \times \text{lcm}(A, B) = A \times B\]

Because $\min(a, b) + \max(a, b) = a + b$ for every exponent. The product of GCD and LCM equals the product of the original numbers. Useful for computing LCM when you already have the GCD:

\[\text{lcm}(A, B) = \frac{A \times B}{\gcd(A, B)}\]

The Euclidean Algorithm

In practice, you don't factorize numbers to compute GCD. You use the Euclidean algorithm:

\[\gcd(a, b) = \gcd(b, \, a \bmod b)\]

Repeat until $b = 0$. The remaining $a$ is the GCD.

int gcd(int a, int b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

This runs in $O(\log(\min(a, b)))$ — much faster than factorizing. Most languages have a built-in: __gcd(a, b) in C++, math.gcd(a, b) in Python.

The set interpretation is for understanding. The Euclidean algorithm is for computing.

Modular Arithmetic

When a problem says "output the answer modulo $10^9 + 7$," it's asking you to work in modular arithmetic. The key properties:

\[(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$$ $$(a \times b) \bmod m = ((a \bmod m) \times (b \bmod m)) \bmod m\]

Addition and multiplication "pass through" the modulus. You can take the mod at any point during computation without affecting the result. This prevents overflow when working with large numbers.

Subtraction works too, but watch for negatives:

\[(a - b) \bmod m = ((a \bmod m) - (b \bmod m) + m) \bmod m\]

The + m ensures a non-negative result.

Division is where things get tricky. You can't just divide under a modulus. Instead, you multiply by the modular inverse — and that's where Fermat's theorem comes in.

Modular Inverse and Fermat's Little Theorem

The Problem

You need to compute $\frac{a}{b} \bmod p$. Division doesn't work directly with modular arithmetic. You need $b^{-1} \bmod p$ — a number $x$ such that $b \times x \equiv 1 \pmod{p}$.

Then $\frac{a}{b} \bmod p = a \times b^{-1} \bmod p$.

Fermat's Little Theorem

If $p$ is prime and $\gcd(a, p) = 1$ (i.e., $p$ doesn't divide $a$), then:

\[a^{p-1} \equiv 1 \pmod{p}\]

This means:

\[a \times a^{p-2} \equiv 1 \pmod{p}\]

So $a^{-1} \equiv a^{p-2} \pmod{p}$.

The modular inverse of $a$ is just $a^{p-2} \bmod p$. Compute it with fast exponentiation.

Fast Exponentiation

Computing $a^{p-2}$ naively would take $O(p)$ multiplications — way too slow for $p = 10^9 + 7$. But you can do it in $O(\log p)$ using repeated squaring:

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;
}

// Modular inverse (p must be prime, gcd(a, p) = 1)
long long modInverse(long long a, long long p) {
    return power(a, p - 2, p);
}

Example: compute $3^{-1} \bmod 7$.

$3^{7-2} = 3^5 = 243$. $243 \bmod 7 = 243 - 34 \times 7 = 243 - 238 = 5$.

Check: $3 \times 5 = 15$. $15 \bmod 7 = 1$. ✓

When Does This Work?

Fermat's theorem requires $p$ to be prime. The modulus $10^9 + 7$ is prime — that's why competitive programming uses it. If the modulus isn't prime, you need the Extended Euclidean Algorithm instead (which works whenever $\gcd(a, m) = 1$).

Cyclicity of Powers

Here's a pattern worth knowing. Take a base $a$ and a prime modulus $p$, and compute $a^1, a^2, a^3, \ldots$ modulo $p$:

For $a = 2, p = 7$:

$k$	$2^k \bmod 7$
1	2
2	4
3	1
4	2
5	4
6	1

The sequence repeats: $2, 4, 1, 2, 4, 1, \ldots$ with period 3.

By Fermat's theorem, $a^{p-1} \equiv 1 \pmod{p}$, so the cycle length always divides $p - 1$. Here, $p - 1 = 6$, and the cycle length 3 divides 6.

This cyclicity is useful for problems that ask "what is $a^n \bmod p$ for astronomically large $n$?" — reduce $n$ modulo the cycle length first.

Euler's Totient Function

What It Counts

$\phi(M)$ is the count of integers from 1 to $M$ that are coprime to $M$ (i.e., $\gcd(k, M) = 1$).

Examples:

$\phi(1) = 1$. Just the number 1 itself.
$\phi(6) = 2$. The numbers 1 and 5 are coprime to 6. (2, 3, 4 share a factor with 6.)
$\phi(7) = 6$. Since 7 is prime, every number from 1 to 6 is coprime to it.
$\phi(p) = p - 1$ for any prime $p$. (This is exactly Fermat's theorem — there are $p-1$ numbers coprime to $p$.)

The Formula

If $M = p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_k^{a_k}$, then:

\[\phi(M) = M \times \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right)\]

For $M = 12 = 2^2 \times 3$:

\[\phi(12) = 12 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4\]

Check: the numbers coprime to 12 from 1 to 12 are 1, 5, 7, 11. Four of them. ✓

Why the Formula Works

The formula uses inclusion-exclusion, but the multiplicative form hides it nicely.

Start with $M$ numbers (1 through $M$). Remove the multiples of each prime factor:

Remove multiples of $p_1$: subtract $M/p_1$.
Remove multiples of $p_2$: subtract $M/p_2$.
But multiples of both $p_1$ and $p_2$ were removed twice — add back $M/(p_1 p_2)$.
Continue for all subsets of prime factors.

That's inclusion-exclusion. But notice what happens when you expand the product:

\[M \times \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) = M \times \left(1 - \frac{1}{p_1} - \frac{1}{p_2} + \frac{1}{p_1 p_2}\right)\]

\[= M - \frac{M}{p_1} - \frac{M}{p_2} + \frac{M}{p_1 p_2}\]

That's exactly inclusion-exclusion. The product form is just a compact way to write it. And the order of multiplication doesn't matter — the result is the same regardless of which prime factor you process first.

Computing phi(M) for a Single Number

Use the factorization approach: find all prime factors, apply the formula.

int eulerTotient(int n) {
    int result = n;
    for (int i = 2; (long long)i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) n /= i;
            result -= result / i;  // multiply by (1 - 1/i)
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

The key line is result -= result / i, which is equivalent to result = result * (1 - 1/i) using integer arithmetic. This works because at each step, result is guaranteed to be divisible by $i$ — a consequence of the prime structure.

Complexity: $O(\sqrt{M})$, since we iterate over potential factors up to $\sqrt{M}$.

Computing phi for All Numbers Up to N: The Sieve

If you need $\phi(k)$ for every $k$ from 1 to $N$, a sieve approach runs in $O(N \log N)$:

vector<int> phi(N + 1);
iota(phi.begin(), phi.end(), 0);  // phi[i] = i initially

for (int i = 2; i <= N; i++) {
    if (phi[i] == i) {  // i is prime (hasn't been modified)
        for (int j = i; j <= N; j += i) {
            phi[j] -= phi[j] / i;  // multiply by (1 - 1/i)
        }
    }
}

How it works:

Initialize $\phi[i] = i$ for all $i$.
For each prime $i$ (detected by $\phi[i] == i$ — it hasn't been modified by any smaller prime), iterate through all multiples of $i$ and apply the factor $(1 - 1/i)$.
By the time you finish, every number has been visited by all its prime factors, and $\phi[k]$ holds the correct value.

Let's trace for $N = 10$:

After prime	$\phi[1..10]$
Initial	1, 2, 3, 4, 5, 6, 7, 8, 9, 10
$p = 2$	1, 1, 3, 2, 5, 3, 7, 4, 9, 5
$p = 3$	1, 1, 2, 2, 5, 2, 7, 4, 6, 5
$p = 5$	1, 1, 2, 2, 4, 2, 7, 4, 6, 4
$p = 7$	1, 1, 2, 2, 4, 2, 6, 4, 6, 4

Final: $\phi = [-, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4]$. All correct.

A Limitation: No Incremental Extension

What if you've computed $\phi$ for all numbers up to $N$ and now need $\phi(N+1)$? Can you extend the sieve by one entry?

No — not efficiently. The sieve works by iterating from primes to their multiples. Given a number, you can't efficiently find which primes generated it without factorizing it. So for individual numbers outside the sieved range, the $O(\sqrt{M})$ factorization approach is the best you can do.

Euler's Theorem (Generalized Fermat)

Fermat's Little Theorem says $a^{p-1} \equiv 1 \pmod{p}$ when $p$ is prime. Euler's theorem generalizes this to any modulus:

\[a^{\phi(m)} \equiv 1 \pmod{m} \quad \text{when } \gcd(a, m) = 1\]

When $m$ is prime, $\phi(m) = m - 1$, and this reduces to Fermat's theorem.

This means the modular inverse of $a$ modulo $m$ (not necessarily prime) is $a^{\phi(m) - 1} \bmod m$ — as long as $\gcd(a, m) = 1$.

Quick Reference

Tool	What It Does	Complexity
Euclidean algorithm	$\gcd(a, b)$	$O(\log \min(a, b))$
LCM via GCD	$\text{lcm}(a, b) = ab / \gcd(a,b)$	$O(\log \min(a, b))$
Fast exponentiation	$a^n \bmod m$	$O(\log n)$
Modular inverse (prime $p$)	$a^{-1} \equiv a^{p-2} \pmod{p}$	$O(\log p)$
Euler's totient (single $M$)	$\phi(M)$	$O(\sqrt{M})$
Euler's totient sieve (1 to $N$)	$\phi(k)$ for all $k \le N$	$O(N \log N)$
Primality test	Is $n$ prime?	$O(\sqrt{n})$
Sieve of Eratosthenes	All primes up to $N$	$O(N \log \log N)$

What's Next

This page and Primes and Factorization cover the core number theory toolkit. The session mentioned that topics like the Chinese Remainder Theorem, Extended Euclidean Algorithm, and advanced factorization methods ($O(N^{1/4})$ for very large numbers) will be covered in a future session.

Tool	What It Does	Complexity
Euclidean algorithm	\(\gcd(a, b)\)	\(O(\log \min(a, b))\)
LCM via GCD	\(\text{lcm}(a, b) = ab / \gcd(a,b)\)	\(O(\log \min(a, b))\)
Fast exponentiation	\(a^n \bmod m\)	\(O(\log n)\)
Modular inverse (prime \(p\))	\(a^{-1} \equiv a^{p-2} \pmod{p}\)	\(O(\log p)\)
Euler's totient (single \(M\))	\(\phi(M)\)	\(O(\sqrt{M})\)
Euler's totient sieve (1 to \(N\))	\(\phi(k)\) for all \(k \le N\)	\(O(N \log N)\)
Primality test	Is \(n\) prime?	\(O(\sqrt{n})\)
Sieve of Eratosthenes	All primes up to \(N\)	\(O(N \log \log N)\)

After prime	\(\phi[1..10]\)
Initial	1, 2, 3, 4, 5, 6, 7, 8, 9, 10
\(p = 2\)	1, 1, 3, 2, 5, 3, 7, 4, 9, 5
\(p = 3\)	1, 1, 2, 2, 5, 2, 7, 4, 6, 5
\(p = 5\)	1, 1, 2, 2, 4, 2, 7, 4, 6, 4
\(p = 7\)	1, 1, 2, 2, 4, 2, 6, 4, 6, 4

\(k\)	\(2^k \bmod 7\)
1	2
2	4
3	1
4	2
5	4
6	1