Euler's Totient Function and Applications

Euler's Totient Function

phi(n) = count of integers in [1, n] coprime to n.

Key properties:

phi(prime p) = p - 1
phi(p^k) = p^k - p^(k-1)
phi is multiplicative: phi(mn) = phi(m)*phi(n) when gcd(m,n)=1
Fermat's little theorem: a^phi(n) ≡ 1 (mod n) when gcd(a,n)=1

Python Implementation

def phi(n):
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

# Sieve for all phi values up to n
def phi_sieve(n):
    phi = list(range(n + 1))
    for p in range(2, n + 1):
        if phi[p] == p:  # p is prime
            for m in range(p, n + 1, p):
                phi[m] -= phi[m] // p
    return phi

# Sum of totients from 1 to n: useful in number theory
def sum_totients(n):
    phi = phi_sieve(n)
    return sum(phi[1:n+1])

print(phi(12))   # 4 (coprime: 1, 5, 7, 11)
print(phi(7))    # 6 (prime: p-1)

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int phi(int n) {
    int result = n;
    for (int p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            result -= result / p;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

vector<int> phiSieve(int n) {
    vector<int> phi(n + 1);
    iota(phi.begin(), phi.end(), 0);
    for (int p = 2; p <= n; p++) {
        if (phi[p] == p) { // prime
            for (int m = p; m <= n; m += p)
                phi[m] -= phi[m] / p;
        }
    }
    return phi;
}

Java Implementation

public class Totient {
    public static int phi(int n) {
        int result = n;
        for (int p = 2; p * p <= n; p++) {
            if (n % p == 0) {
                while (n % p == 0) n /= p;
                result -= result / p;
            }
        }
        if (n > 1) result -= result / n;
        return result;
    }
}

Applications

Modular inverse: a^(-1) mod p = a^(phi(p)-1) mod p = a^(p-2) mod p
RSA encryption: phi(n) = phi(p)phi(q) = (p-1)(q-1) for key generation
Primitive roots: g is primitive root mod n if g^phi(n)/p != 1 mod n for all prime p | phi(n)

Complexity

Single n: O(sqrt n)
Sieve to n: O(n log log n)