Euler's Totient Function & Euler's Theorem
Euler's Totient Function phi(n) counts integers in [1, n] coprime to n, generalizing Fermat's Little Theorem to composite moduli via Euler's Theorem a^phi(m) ≡ 1 (mod m) and underpinning RSA cryptography.
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
Euler's Totient Function & Euler's Theorem
Euler's Totient Function $\varphi(n)$ counts the number of integers in $\{1, 2, \dots, n\}$ that are coprime to $n$ (i.e., $\gcd(k, n) = 1$). Using the prime factorization $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$, it has the closed product formula:
$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$
Euler's Theorem generalizes Fermat's Little Theorem to any modulus $m$ (even composite): if $\gcd(a, m) = 1$, then $a^{\varphi(m)} \equiv 1 \pmod m$—the mathematical foundation of RSA encryption!
At a Glance
| Operation | Time Complexity | Space |
| :--- | :--- | :--- |
| Single $\varphi(n)$ | $O(\sqrt{n})$ | $O(1)$ |
| All $\varphi(1..N)$ (Totient Sieve) | $O(N \log \log N)$ | $O(N)$ |
| Composite Modular Inverse | $O(\sqrt{m} + \log m)$ via $a^{\varphi(m)-1} \bmod m$ | $O(1)$ |
---
How It Works
Single $\varphi(n)$ in $O(\sqrt{n})$
1. Start with result = n.
2. For each factor p = 2 while p * p <= n:
- If
pdividesn, strip all powers ofp(while (n % p == 0) n /= p) and applyresult -= result / p.
3. If n > 1 remains (it's a prime factor
Loading AntInLoop...
result -= result / n.
All $\varphi(1..N)$ via Sieve in $O(N \log \log N)$
1. Initialize phi[i] = i for all $1 \le i \le N$.
2. For p = 2..N: if phi[p] == p (p is prime!), loop over multiples m = p, 2p, 3p, ... <= N and set phi[m] -= phi[m] / p.
Step-by-Step Trace ($\varphi(12)$)
12 = 2^2 * 3:result = 12- Prime
2:result = 12 - 12/2 = 6 - Prime
3:result = 6 - 6/3 = 4 - Indeed, the 4 numbers in
1..12coprime to12are{1, 5, 7, 11}!
---
Complexity & Key Insights
- Gauss's Divisor Sum Property: $\sum_{d \mid n} \varphi(d) = n$! (For $n = 12$: $\varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)+\varphi(6)+\varphi(12) = 1+1+2+2+2+4 = 12$.)
- Generalized Euler's Theorem (Even When $\gcd(a, m) > 1$): For any $k \ge \log_2 m$:
$a^k \equiv a^{(k \bmod \varphi(m)) + \varphi(m)} \pmod m$
This lets you evaluate nested power towers modulo composite $m$!
---
Practice Problems
Easy
1. Compute $\varphi(n)$ in $O(\sqrt{n})$
Given $n \le 10^{12}$, compute Euler's Totient $\varphi(n)$.
Approach: Trial-divide prime factors up to $\sqrt{n}$, updating res -= res / p. Time: $O(\sqrt{n})$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
long long phi(long long n) {
long long res = n;
for (long long p = 2; p * p <= n; ++p) {
if (n % p == 0) {
while (n % p == 0) n /= p;
res -= res / p;
}
}
if (n > 1) res -= res / n;
return res;
}
int main() {
std::cout << phi(12) << " " << phi(36) << " " << phi(97) << "\n"; // 4 12 96
return 0;
}
</details>
2. Totient Sieve: Compute $\varphi(1..N)$ in $O(N \log \log N)$
Precompute $\varphi(i)$ for every $1 \le i \le N$ using a sieve.
Approach: Initialize phi[i] = i; for each prime p (phi[p] == p), update every multiple m via phi[m] -= phi[m] / p. Time: $O(N \log \log N)$. Space: $O(N)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <numeric>
#include <vector>
std::vector<int> phiSieve(int n) {
std::vector<int> phi(n + 1);
std::iota(phi.begin(), phi.end(), 0);
for (int p = 2; p <= n; ++p) {
if (phi[p] == p) {
for (int m = p; m <= n; m += p) {
phi[m] -= phi[m] / p;
}
}
}
return phi;
}
int main() {
auto p = phiSieve(10);
for (int i = 1; i <= 10; ++i) std::cout << p[i] << " ";
std::cout << "\n"; // 1 1 2 2 4 2 6 4 6 4
return 0;
}
</details>
---
Intermediate
3. Count Reduced Proper Fractions with Denominator $\le N$ (Farey Sequence Length)
Count how many reduced fractions $a / b$ satisfy $0 < a < b \le N$ (i.e., $\gcd(a, b) = 1$).
Approach: For each denominator $b \ge 2$, there are exactly $\varphi(b)$ valid numerators $a < b$ coprime to $b$. Sum $\sum_{b=2}^{N} \varphi(b)$ via the Totient Sieve! Time: $O(N \log \log N)$. Space: $O(N)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <numeric>
#include <vector>
long long countReducedFractions(int n) {
std::vector<int> phi(n + 1);
std::iota(phi.begin(), phi.end(), 0);
for (int p = 2; p <= n; ++p) {
if (phi[p] == p) {
for (int m = p; m <= n; m += p) phi[m] -= phi[m] / p;
}
}
long long total = 0;
for (int b = 2; b <= n; ++b) total += phi[b];
return total;
}
int main() {
std::cout << countReducedFractions(5) << "\n"; // 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5 -> 9
return 0;
}
</details>
4. Modular Inverse Modulo Any Composite $m$ Using Euler's Theorem
Compute $a^{-1} \bmod m$ (when $\gcd(a, m) = 1$) using $a^{\varphi(m) - 1} \bmod m$.
Approach: Check $\gcd(a, m) == 1$, compute $\varphi(m)$, and return modPow(a, phi(m) - 1, m). Time: $O(\sqrt{m} + \log m)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <numeric>
long long phi(long long n) {
long long res = n;
for (long long p = 2; p * p <= n; ++p) {
if (n % p == 0) {
while (n % p == 0) n /= p;
res -= res / p;
}
}
if (n > 1) res -= res / n;
return res;
}
long long modPow(long long a, long long e, long long m) {
long long res = 1 % m;
for (a %= m; e > 0; e >>= 1, a = a * a % m)
if (e & 1) res = res * a % m;
return res;
}
long long modInvEuler(long long a, long long m) {
if (std::gcd(a, m) != 1) return -1;
return modPow(a, phi(m) - 1, m);
}
int main() {
std::cout << modInvEuler(7, 26) << " " << modInvEuler(4, 12) << "\n"; // 15 -1
return 0;
}
</details>
---
Hard
5. Sum of $\gcd(k, n)$ for $k = 1..n$ (Pillai's Arithmetical Function)
Compute $\sum_{k=1}^{n} \gcd(k, n)$ for $n \le 10^{12}$ in $O(\sqrt{n})$ time!
Approach: Group terms by $d = \gcd(k, n)$ (where $d \mid n$). How many $k \in [1, n]$ have $\gcd(k, n) = d$? Exactly the count of $k' = k / d \in [1, n / d]$ with $\gcd(k', n / d) = 1$, which is $\varphi(n / d)$! Thus:
$\sum_{k=1}^{n} \gcd(k, n) = \sum_{d \mid n} d \cdot \varphi\!\left(\frac{n}{d}\right)$
Iterate over divisors $d \le \sqrt{n}$ and accumulate both $d$ and $n / d$. Time: $O(\sqrt{n} \cdot d(n))$ (fast even for $n = 10^{12}$).
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
long long phi(long long n) {
long long res = n;
for (long long p = 2; p * p <= n; ++p) {
if (n % p == 0) {
while (n % p == 0) n /= p;
res -= res / p;
}
}
if (n > 1) res -= res / n;
return res;
}
long long gcdSum(long long n) {
long long sum = 0;
for (long long d = 1; d * d <= n; ++d) {
if (n % d == 0) {
sum += d * phi(n / d);
if (d != n / d) sum += (n / d) * phi(d);
}
}
return sum;
}
int main() {
// n = 6: gcd(1..6, 6) = 1 + 2 + 3 + 2 + 1 + 6 = 15
std::cout << gcdSum(6) << " " << gcdSum(12) << "\n"; // 15 40
return 0;
}
</details>
---
Related Algorithms
- Fermat's Little Theorem — prime-modulus special case of Euler's Theorem ($\varphi(p) = p - 1$).
- Sieve of Eratosthenes — shares the exact sieve structure used by the Totient Sieve.
- GCD & LCM — coprimality ($\gcd(k, n) = 1$) defines $\varphi(n)$.