Euler's Totient Function
Pillar: Set — "\(\phi(n)\) is the SIZE of the set \(\{k \in [1,n] : \gcd(k,n) = 1\}\). The product formula falls out from inclusion-exclusion on prime factors."
The Setup
You need to compute \(2^{3^{4}} \bmod 10^9 + 7\). The exponent \(3^4 = 81\) is manageable, but what if the problem says \(a^{b^c} \bmod m\) where \(b^c\) has billions of digits? You can't even store the exponent, let alone feed it to modpow.
The escape hatch is Euler's theorem: under the right conditions, you can reduce a massive exponent modulo a much smaller number — \(\phi(m)\) — and get the same answer. But first you need to know what \(\phi\) is, how to compute it, and why it works.
Start with a small example. Take \(n = 12\). Which integers from \(1\) to \(12\) share no common factor with \(12\)? Check each one:
| \(k\) | \(\gcd(k, 12)\) | Coprime? |
|---|---|---|
| 1 | 1 | Yes |
| 2 | 2 | No |
| 3 | 3 | No |
| 4 | 4 | No |
| 5 | 1 | Yes |
| 6 | 6 | No |
| 7 | 1 | Yes |
| 8 | 4 | No |
| 9 | 3 | No |
| 10 | 2 | No |
| 11 | 1 | Yes |
| 12 | 12 | No |
The survivors are \(\{1, 5, 7, 11\}\). Four of them. So \(\phi(12) = 4\).
Definition
Euler's totient function \(\phi(n)\) counts how many integers in \(\{1, 2, \ldots, n\}\) are coprime to \(n\):
A few small values to build intuition:
- \(\phi(1) = 1\) — the set is \(\{1\}\), and \(\gcd(1, 1) = 1\).
- \(\phi(6) = 2\) — the set is \(\{1, 5\}\). The numbers \(2, 3, 4, 6\) all share a factor with \(6\).
- \(\phi(12) = 4\) — as computed above: \(\{1, 5, 7, 11\}\).
- \(\phi(p) = p - 1\) for any prime \(p\) — every number from \(1\) to \(p - 1\) is coprime to \(p\), since \(p\) has no smaller divisors.
That last one is important. For primes, the totient is trivial. The interesting behavior happens with composites.
The Product Formula
Computing \(\phi(n)\) by checking every \(k\) from \(1\) to \(n\) is \(O(n \log n)\) with GCD calls. There's a closed-form formula that's much faster.
The product formula:
where the product runs over the distinct prime factors of \(n\).
Derivation via Inclusion-Exclusion
This is where the Set pillar earns its keep. The idea: instead of counting the integers coprime to \(n\), count the ones that are NOT coprime and subtract.
Take \(n = 12 = 2^2 \times 3\). The prime factors are \(2\) and \(3\). An integer \(k \in [1, 12]\) is NOT coprime to \(12\) exactly when \(2 \mid k\) or \(3 \mid k\).
By inclusion-exclusion on the set of multiples:
So \(\phi(12) = 12 - 8 = 4\). Matches.
Now generalize. If \(n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_r^{a_r}\), the count of integers in \([1, n]\) divisible by prime \(p_i\) is \(n / p_i\). The count divisible by both \(p_i\) and \(p_j\) is \(n / (p_i p_j)\). And so on. Inclusion-exclusion gives:
Factor out \(n\):
Expand the right side — each term in the expansion corresponds to exactly one subset of prime factors, with the correct sign from inclusion-exclusion. The two expressions are identical.
Worked Example
\(\phi(12)\). Factor: \(12 = 2^2 \times 3\). Distinct primes: \(2, 3\).
Another: \(\phi(30)\). Factor: \(30 = 2 \times 3 \times 5\).
The coprime set is \(\{1, 7, 11, 13, 17, 19, 23, 29\}\). Eight elements.
Key Values and Special Cases
Prime: \(\phi(p) = p - 1\).
This falls directly from the product formula: \(\phi(p) = p \times (1 - 1/p) = p - 1\). Or just note that every integer from \(1\) to \(p - 1\) is coprime to a prime.
Prime power: \(\phi(p^k) = p^{k-1}(p - 1) = p^k - p^{k-1}\).
The only integers in \([1, p^k]\) that share a factor with \(p^k\) are the multiples of \(p\): there are \(p^{k-1}\) of them. So \(\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)\).
Equivalently from the product formula: \(\phi(p^k) = p^k \times (1 - 1/p) = p^k - p^{k-1}\).
Example: \(\phi(8) = \phi(2^3) = 2^2 \times (2 - 1) = 4\). The coprime set is \(\{1, 3, 5, 7\}\).
Multiplicative Property
If \(\gcd(a, b) = 1\), then:
This says \(\phi\) is a multiplicative function — it respects products of coprime arguments.
Why? By the Chinese Remainder Theorem (which you may encounter later), there's a bijection between residues mod \(ab\) and pairs of residues mod \(a\) and mod \(b\). A residue is coprime to \(ab\) exactly when it's coprime to both \(a\) and \(b\). So the count of coprime residues mod \(ab\) equals the product of counts mod \(a\) and mod \(b\).
This property, combined with the prime power formula, gives you the product formula for free. Factor \(n = p_1^{a_1} \cdots p_r^{a_r}\). Since the prime powers are pairwise coprime:
The Divisor Sum Identity
Here's a result that looks surprising but has an elegant proof:
For \(n = 12\), the divisors are \(1, 2, 3, 4, 6, 12\):
Proof. Partition the set \(\{1, 2, \ldots, n\}\) by GCD with \(n\). For each divisor \(d\) of \(n\), let \(S_d = \{k \in [1, n] : \gcd(k, n) = d\}\). These sets are disjoint and cover all of \(\{1, \ldots, n\}\), so \(\sum_{d \mid n} |S_d| = n\).
Now, \(\gcd(k, n) = d\) if and only if \(\gcd(k/d, n/d) = 1\). As \(k\) ranges over multiples of \(d\) in \([1, n]\), the value \(k/d\) ranges over \([1, n/d]\). So \(|S_d| = \phi(n/d)\).
Therefore \(\sum_{d \mid n} \phi(n/d) = n\). Since \(d\) ranges over all divisors of \(n\), so does \(n/d\) — the sum \(\sum_{d \mid n} \phi(n/d)\) is the same as \(\sum_{d \mid n} \phi(d)\).
Computing \(\phi(n)\) for a Single Value
Factor \(n\) by trial division, then apply the product formula. In code, the trick is to use integer arithmetic to avoid floating point: instead of multiplying by \((1 - 1/p)\), compute result -= result / factor which is equivalent to multiplying by \((p - 1)/p\).
Walk through \(n = 60\):
- Initialize
result = 60,value = 60. - \(2 \mid 60\): divide out all \(2\)s (\(60 \to 15\)). Apply:
result -= result / 2\(\to\) \(60 - 30 = 30\). - \(3 \mid 15\): divide out all \(3\)s (\(15 \to 5\)). Apply:
result -= result / 3\(\to\) \(30 - 10 = 20\). - \(5 \mid 5\): divide out (\(5 \to 1\)). Apply:
result -= result / 5\(\to\) \(20 - 4 = 16\). - Remaining value is \(1\), so done. \(\phi(60) = 16\).
Check: \(60 \times \frac{1}{2} \times \frac{2}{3} \times \frac{4}{5} = 16\). Correct.
Time complexity: \(O(\sqrt{n})\) — same as trial division factorization.
Sieve for All \(\phi\) Values
When you need \(\phi(k)\) for every \(k\) from \(1\) to some limit, trial-dividing each one individually is \(O(n\sqrt{n})\). A sieve does it in \(O(n \log \log n)\) — the same complexity as the Sieve of Eratosthenes.
The idea: initialize phi[i] = i for all \(i\). Then for each prime \(p\) (detected when phi[p] still equals \(p\)), iterate over all multiples of \(p\) and apply phi[multiple] -= phi[multiple] / p. Each prime applies its \((1 - 1/p)\) factor to all its multiples, and since each integer is touched once per distinct prime factor, the total work is \(O(n \log \log n)\).
Trace for limit \(= 10\):
| After prime | phi[1..10] |
|---|---|
| Init | 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, \phi(2) = 1, \phi(3) = 2, \phi(4) = 2, \phi(5) = 4, \phi(6) = 2, \phi(7) = 6, \phi(8) = 4, \phi(9) = 6, \phi(10) = 4\).
Euler's Theorem
This is the payoff. Euler's theorem generalizes Fermat's Little Theorem to any modulus — not just primes.
Euler's theorem: If \(\gcd(a, m) = 1\), then:
When \(m = p\) is prime, \(\phi(p) = p - 1\), and this reduces to Fermat's Little Theorem: \(a^{p-1} \equiv 1 \pmod{p}\). Euler's theorem is the generalization to composite moduli.
Example: \(\phi(12) = 4\). Take \(a = 5\), which is coprime to \(12\):
The condition \(\gcd(a, m) = 1\) is essential. If \(a\) shares a factor with \(m\), the theorem does not hold. For instance, \(\gcd(2, 12) = 2 \neq 1\), and \(2^4 = 16 \equiv 4 \pmod{12}\), not \(1\).
Exponent Reduction
Euler's theorem unlocks exponent reduction: when the exponent is astronomically large, you can shrink it.
The basic reduction. If \(\gcd(a, m) = 1\):
Why? Write \(b = q \cdot \phi(m) + r\) where \(r = b \bmod \phi(m)\). Then:
CSES Exponentiation II
The problem: given \(a\), \(b\), \(c\), compute \(a^{b^c} \bmod (10^9 + 7)\).
The exponent \(b^c\) can be enormous — up to \((10^9)^{(10^9)}\), a number with billions of digits. You can't compute it directly.
Since \(10^9 + 7\) is prime and \(a\) is at most \(10^9\), either \(a \equiv 0 \pmod{10^9 + 7}\) (answer is \(0\)) or \(\gcd(a, 10^9 + 7) = 1\). In the coprime case, apply exponent reduction:
Since \(\phi(10^9 + 7) = 10^9 + 6\) (it's prime), you need \(b^c \bmod (10^9 + 6)\). This is a standard modpow call. Then feed that reduced exponent into another modpow call.
Two steps:
1. Compute reducedExponent = modpow(b, c, phi(mod)).
2. Compute answer = modpow(a, reducedExponent, mod).
The General Case: When \(\gcd(a, m) \neq 1\)
The basic reduction \(a^b \equiv a^{b \bmod \phi(m)}\) requires \(\gcd(a, m) = 1\). When that fails, you need the generalized formula:
The key difference: when \(b \geq \phi(m)\), you reduce the exponent modulo \(\phi(m)\) and then ADD \(\phi(m)\) back. This ensures the exponent is large enough for the formula to hold, regardless of whether \(a\) and \(m\) share factors.
For CSES Exponentiation II with \(m = 10^9 + 7\) (prime), the only case where \(\gcd(a, m) \neq 1\) is \(a \equiv 0 \pmod{m}\), which gives answer \(0\) (assuming \(b^c > 0\)). So the basic reduction suffices. But for problems with composite moduli, the generalized form is essential.
The Code
Single Value Totient
long long eulerTotient(long long value) {
long long result = value;
for (long long factor = 2; factor * factor <= value; factor++) {
if (value % factor == 0) {
while (value % factor == 0) value /= factor;
result -= result / factor;
}
}
if (value > 1) result -= result / value;
return result;
}
\(O(\sqrt{n})\) time, \(O(1)\) space.
The line result -= result / factor is the integer version of multiplying by \((1 - 1/p)\). If result is currently \(r\) and the prime factor is \(p\), then \(r - r/p = r \cdot (p-1)/p\). The integer division is exact here because \(p\) was already applied as a factor of the original value, guaranteeing divisibility.
The if (value > 1) at the end handles the case where \(n\) has a prime factor larger than \(\sqrt{n}\) — there can be at most one such factor.
Sieve Totient
vector<long long> sieveTotient(int limit) {
vector<long long> phi(limit + 1);
iota(phi.begin(), phi.end(), 0);
for (int prime = 2; prime <= limit; prime++) {
if (phi[prime] == prime) {
for (int multiple = prime; multiple <= limit; multiple += prime) {
phi[multiple] -= phi[multiple] / prime;
}
}
}
return phi;
}
\(O(n \log \log n)\) time, \(O(n)\) space.
The detection phi[prime] == prime works because a prime \(p\) is never modified by any smaller prime — its initial value \(p\) survives intact until we reach it in the outer loop. Composites get modified by their smaller prime factors first, so phi[composite] < composite by the time we reach them.
Modpow with Huge Exponent Tower
Using the modpow function from Ch4 L2:
long long modpow(long long base, long long exponent, long long mod) {
long long result = 1;
base %= mod;
while (exponent > 0) {
if (exponent & 1) result = result * base % mod;
base = base * base % mod;
exponent >>= 1;
}
return result;
}
long long modpowHugePower(long long base, long long midExponent, long long topExponent, long long mod) {
long long phiMod = eulerTotient(mod);
long long reducedExponent = modpow(midExponent, topExponent, phiMod);
return modpow(base, reducedExponent, mod);
}
\(O(\sqrt{m} + \log c + \log \phi(m))\) time for the full computation: \(O(\sqrt{m})\) to compute \(\phi(m)\), \(O(\log c)\) for the first modpow, and \(O(\log \phi(m))\) for the second.
For the generalized case (when \(\gcd(a, m) \neq 1\) is possible), replace the reduction step:
long long modpowHugePowerGeneral(long long base, long long midExponent, long long topExponent, long long mod) {
long long phiMod = eulerTotient(mod);
long long reducedExponent = modpow(midExponent, topExponent, phiMod);
if (topExponent > 0 && reducedExponent == 0) reducedExponent = phiMod;
return modpow(base, reducedExponent, mod);
}
The trick: if \(b^c\) is positive and \(b^c \bmod \phi(m) = 0\), the true exponent is a nonzero multiple of \(\phi(m)\), so use \(\phi(m)\) instead of \(0\). This implements the \(b \bmod \phi(m) + \phi(m)\) rule when \(b \geq \phi(m)\), since any \(b^c > 0\) with \(c > 0\) satisfies \(b^c \geq b \geq 2 > \phi(m)\) in all nontrivial cases where the correction matters.
Common Mistakes
-
Forgetting the general case. The reduction \(a^b \equiv a^{b \bmod \phi(m)}\) only works when \(\gcd(a, m) = 1\). With composite \(m\), you must use the generalized formula — add \(\phi(m)\) back when \(b \geq \phi(m)\). The CSES problem dodges this because \(m\) is prime, but many CF problems use composite moduli.
-
Computing \(\phi\) of a prime incorrectly. If \(m\) is prime, \(\phi(m) = m - 1\), not \(m\). Off-by-one here means your exponent reduction is wrong and every answer is garbage.
-
Using
intfor the sieve when values overflow. \(\phi(n)\) can be as large as \(n - 1\) (when \(n\) is prime). If your sieve limit is \(10^7\) or more,intis fine. But the intermediate products in the single-value function can overflowint— always uselong long.
Quick Recap
- \(\phi(n)\) counts integers in \([1, n]\) coprime to \(n\). It's the size of a set — the Set pillar.
- Product formula: \(\phi(n) = n \prod_{p \mid n}(1 - 1/p)\). Derived by inclusion-exclusion on prime factor multiples.
- Key values: \(\phi(p) = p - 1\), \(\phi(p^k) = p^{k-1}(p-1)\), \(\phi\) is multiplicative over coprime arguments.
- Euler's theorem: \(a^{\phi(m)} \equiv 1 \pmod{m}\) when \(\gcd(a, m) = 1\). Generalizes Fermat.
- Exponent reduction: \(a^b \equiv a^{b \bmod \phi(m)} \pmod{m}\) (coprime case). For the general case, add \(\phi(m)\) back when \(b \geq \phi(m)\).
Problems
| Problem | Link | Difficulty | Focus |
|---|---|---|---|
| CSES — Exponentiation II | cses.fi/problemset/task/1712 | Medium | Exponent reduction via \(\phi\); two-layer modpow |
| CF 1114F — Please, another Sudoku Coloring | codeforces.com/problemset/problem/1114/F | Hard | Totient on segment tree; multiplicative function queries |
This concludes Chapter 4. Next up: Chapter 5 — Combinatorics and Structured Counting, starting with the counting principles that turn set sizes into formulas.