Euler's Totient Function

By SkytrailGroup Mathematics Editorial Team April 12, 2026

Definition

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

Euler's theorem: \(a^{{\varphi(n)}}\equiv1\pmod{{n}}\) when gcd(a,n)=1.

Examples

Example 1. φ(12).

Solution. 12=2²·3. φ=12·(1−1/2)·(1−1/3)=4.

In Depth

Euler's totient function \(\phi(n)\) counts the integers in \(\{1,\ldots,n\}\) coprime to \(n\). For prime \(p\): \(\phi(p)=p-1\). For prime power: \(\phi(p^k)=p^{k-1}(p-1)\). Multiplicativity: \(\phi(mn)=\phi(m)\phi(n)\) when \(\gcd(m,n)=1\). General formula: \(\phi(n)=n\prod_{p\mid n}(1-1/p)\).

Euler's theorem: \(a^{\phi(n)}\equiv1\pmod{n}\) for \(\gcd(a,n)=1\). This generalizes Fermat's little theorem (\(n=p\) prime, \(\phi(p)=p-1\)). The multiplicative order of \(a\) modulo \(n\) divides \(\phi(n)\).

RSA key generation uses \(\phi(n)\): with \(n=pq\), \(\phi(n)=(p-1)(q-1)\). The public exponent \(e\) satisfies \(\gcd(e,\phi(n))=1\); the private exponent \(d\) satisfies \(ed\equiv1\pmod{\phi(n)}\). Decryption works because \(m^{ed}\equiv m\pmod{n}\) by Euler's theorem.

The sum formula: \(\sum_{d\mid n}\phi(d)=n\). This identity, proved by grouping fractions \(k/n\) by their reduced denominator, is a key tool in number theory. It shows \(\phi\) is the Möbius inversion of the identity function.

The average order of \(\phi(n)\) is \(3n/\pi^2\): \(\frac{1}{N}\sum_{n=1}^N\phi(n)\sim\frac{3N}{\pi^2}\). The constant \(3/\pi^2=6/\pi^2\cdot1/2\) is related to the probability that two random integers are coprime, which equals \(6/\pi^2\).

Key Properties & Applications

Carmichael's function \(\lambda(n)\) is the smallest \(m\) such that \(a^m\equiv1\pmod{n}\) for all \(\gcd(a,n)=1\). It divides \(\phi(n)\) and equals \(\phi(n)\) when \((\mathbb{Z}/n\mathbb{Z})^*\) is cyclic. Using \(\lambda(n)\) instead of \(\phi(n)\) in RSA gives smaller exponents.

The totient function satisfies \(\phi(n)=n\prod_{p|n}(1-1/p)\). For \(n=p_1^{a_1}\cdots p_k^{a_k}\), this is \(\phi(n)=p_1^{a_1-1}(p_1-1)\cdots p_k^{a_k-1}(p_k-1)\). The totient is even for all \(n>2\).

Euler's product formula \(\zeta(s)\prod_p(1-p^{-s})=1\) (where the product is over all primes) is equivalent to the Fundamental Theorem of Arithmetic. It connects the totient function (via the Euler product for \(\phi\)) to the Riemann zeta function.