Euler’s totient function \(\varphi(n)\) refresher

Euler’s totient function \(\varphi(n)\) counts reduced residues modulo \(n\). Standard references: [Apostol, 1976], [Niven et al., 1991].

Definition

For \(n\ge 1\),

\[ \varphi(n) = \#\{\,1\le k\le n : \gcd(k,n)=1\,\}. \]

Equivalently: \(\varphi(n)\) is the size of the multiplicative group \((\mathbb{Z}/n\mathbb{Z})^\times\).

Prime power formula

If \(p\) is prime and \(k\ge 1\),

\[ \varphi(p^k)=p^k-p^{k-1}=p^k\left(1-\frac1p\right). \]

Since \(\varphi\) is multiplicative, for \(n=\prod p_i^{\alpha_i}\):

\[ \varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right). \]

Important properties

• Euler’s theorem: if \(\gcd(a,n)=1\) then \(a^{\varphi(n)}\equiv 1\pmod n\).

• Average order: roughly \(\sum_{n\le x}\varphi(n)\sim \frac{3}{\pi^2}x^2\) (analytic methods).

• Extremes: \(\varphi(n)\) is small when \(n\) has many small prime factors.

Computational notes

Given the prime factorization of \(n\), \(\varphi(n)\) is cheap to compute via the product formula. For experiments, you can often compute it for all \(n\le N\) efficiently using a sieve-style method.

Experiments in this repository

• E101 — Reduced residues (ℤ/qℤ)× as an explicit set; verify size φ(q).