Euler Phi
Count how many integers up to n are coprime to n, and use the factorization formula to turn that count into code.
Euler Phi
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Euler's phi function \(\varphi(n)\) counts how many integers in \([1, n]\) are coprime to \(n\). It shows up in modular arithmetic, counting reduced fractions, cycle lengths, and several multiplicative-function problems.
When to Use It
Use \(\varphi\) when:
the question asks for coprime counts,
Euler's theorem might replace a large exponent,
a multiplicative formula over prime factors is wanted.
Core Idea
If \[ n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}, \] then \[ \varphi(n) = n \prod_{i=1}^{k}\left(1 - \frac{1}{p_i}\right). \]
So once the distinct prime divisors are known, computing \(\varphi(n)\) is straightforward.
Key Insight
Phi is counting by exclusion. Among the numbers \(1\) through \(n\), the only ones that fail to be coprime to \(n\) are those divisible by one of its prime factors. The product formula is inclusion-exclusion compressed into multiplicative form.
Operations / Main Technique
factor \(n\),
start from \(\texttt{result = n}\),
for each distinct prime divisor \(p\), apply \[ \texttt{result -= result / p}. \]
Worked example.
For \(n = 12 = 2^2 \cdot 3\), \[ \varphi(12) = 12\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 4. \] The coprime values are \(1, 5, 7, 11\).
Correctness Intuition
Removing multiples of each distinct prime divisor removes exactly the numbers that share a nontrivial gcd with \(n\). The product formula works because phi is multiplicative on coprime arguments.
Complexity Analysis
If factorization is done by trial division, computing \(\varphi(n)\) is \(O(\sqrt{n})\). With precomputed SPF or a phi sieve for many queries, the per-query or all-values cost can be much better.
Implementation
The code includes:
phi_single(n)from factorization,a linear-style sieve for \(\varphi(1 \dots N)\).
Common Pitfalls
Updating the result once per prime power instead of once per distinct prime.
Using Euler's theorem where the base is not coprime to the modulus.
Recomputing phi from scratch many times when a sieve would be better.
Variants / Extensions
Phi sieve for all values up to \(N\).
Use phi inside modular-exponent cycles.
General multiplicative-function preprocessing alongside Mobius and divisor counts.
Practice Problems
Compute \(\varphi(n)\) for many values.
Count reduced fractions or coprime pairs.
Evaluate large exponents modulo \(m\) with phi-based reasoning.
References
Code
Contest-ready reference implementation for the idea explained above.
long long phi_single(long long n) {
long long result = n;
for (long long p = 2; p * p <= n; ++p) {
if (n % p != 0) continue;
while (n % p == 0) {
n /= p;
}
result -= result / p;
}
if (n > 1) {
result -= result / n;
}
return result;
}
vector<int> phi_sieve(int n) {
vector<int> phi(n + 1);
iota(phi.begin(), phi.end(), 0);
for (int p = 2; p <= n; ++p) {
if (phi[p] != p) continue;
for (int x = p; x <= n; x += p) {
phi[x] -= phi[x] / p;
}
}
return phi;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.