AntInLoop

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 p divides n, strip all powers of p (while (n % p == 0) n /= p) and apply result -= result / p.

3. If n > 1 remains (it's a prime factor

Loading AntInLoop...

gt; \sqrt{n_0}$), apply 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..12 coprime to 12 are {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