Euler Totient Function

$\phi (n)$ counts the integers in $[1,n]$ coprime to $n$.

$\phi (n)=n{\prod }_{p\mid n}\left(1-\frac{1}{p}\right).$

$\phi$ is multiplicative: $\phi (ab)=\phi (a)\phi (b)$ when $\gcd (a,b)=1$, and $\phi (p^k)=p^k-p^{k-1}$.

Computing it

Single value, $O(\sqrt{n})$:

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;                       // res *= (1 - 1/p)
        }
    if (n > 1) res -= res / n;
    return res;
}

All values up to $N$, $O(N\log \log N)$:

vector<int> phi(N + 1);
iota(phi.begin(), phi.end(), 0);
for (int i = 2; i <= N; i++)
    if (phi[i] == i)                              // i is prime
        for (int j = i; j <= N; j += i) phi[j] -= phi[j] / i;

A linear sieve computes it in $O(N)$ alongside the smallest prime factor.

Euler’s theorem

$a^{\phi (n)}\equiv 1(\mathrm{mod}n)\text{when }\gcd (a,n)=1.$

Fermat’s little theorem is the case $n=p$: $a^{p-1}\equiv 1$.

Consequence: exponents can be reduced modulo $\phi (n)$:
$a^k\equiv a^{k\mathrm{mod}\phi (n)}(\mathrm{mod}n)(\gcd (a,n)=1).$

When $\gcd (a,n)\ne 1$ — the generalised theorem

$a^k\equiv a^{\phi (n)+(k\mathrm{mod}\phi (n))}(\mathrm{mod}n)\text{for }k\ge {\log }_{2}n.$

This is what makes power towers computable: to evaluate $a^{b^{c^{\cdots }}}\mathrm{mod}n$, recurse on the exponent modulo $\phi (n)$, then $\phi (\phi (n))$, and so on. The chain $n,\phi (n),\phi (\phi (n)),\dots$ reaches 1 in $O(\log n)$ steps, so the recursion is shallow.

long long tower(vector<long long>& a, int i, long long m) {
    if (m == 1) return 0;
    if (i == (int)a.size()) return 1;
    long long p = phi(m);
    long long e = tower(a, i + 1, p);
    return powmodSafe(a[i], e + p, m);            // add phi(m) to stay in the safe range
}

Key identities

Identity
${\sum }_{d\mid n}\phi (d)=n$	the divisor sum
$\phi (p)=p-1$	for prime $p$
$\phi (p^k)=p^{k-1}(p-1)$
$\phi (2n)=2\phi (n)$ if $n$ even, $\phi (n)$ if odd
$\phi (n)$ is even for $n>2$
${\sum }_{k=1,\gcd (k,n)=1}^{n}k=\frac{n\phi (n)}{2}$	sum of the coprime residues, for $n>1$
$\gcd$-sum: ${\sum }_{k=1}^n\gcd (k,n)={\sum }_{d\mid n}d\phi (n/d)$

The divisor-sum identity ${\sum }_{d\mid n}\phi (d)=n$ is the one that keeps appearing. It says: partition $[1,n]$ by $\gcd (k,n)=d$; the class for $d$ has $\phi (n/d)$ elements.

Where $\phi$ shows up

Problem	Use
Count coprime pairs / fractions in lowest terms	$\sum \phi (i)$ — the Farey sequence length
Multiplicative order, primitive roots	the order divides $\phi (n)$
Modular inverse for composite $m$	$a^{-1}=a^{\phi (m)-1}$
Power towers $a^{b^c}\mathrm{mod}n$	the generalised Euler theorem
Number of generators of a cyclic group of order $n$	$\phi (n)$
Necklace / Burnside counting	${\sum }_{d\mid n}\phi (d){\sigma }^{n/d}/n$
Length of the repeating decimal of $1/n$	the multiplicative order of 10 mod $n$, which divides $\phi (n)$
Counting lattice points visible from the origin	$\phi$-based

Farey / coprime counting

The number of fractions $p/q$ in lowest terms with $1\le p\le q\le n$ is ${\sum }_{i=1}^n\phi (i)$. To compute this sum for $n$ up to $10^{11}$, use the Mertens-style recursion:

$\Phi (n)=\frac{n(n+1)}{2}-{\sum }_{d=2}^n\Phi \left(\lfloor \frac{n}{d}\rfloor \right),$

evaluated with divisor-block grouping and memoisation — $O(n^{2/3})$ with a sieve for small values. This is the standard technique for “sum a multiplicative function up to a huge $n$”.

See also: Möbius Function · Divisor Functions · Primitive Root