Euler's Totient Function

The Euler totient function, denoted \( \varphi(n) \), counts the positive integers up to \( n \) that are relatively prime to \( n \).

Definition

Formally,

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

Properties

• Multiplicative: If \(\gcd(a,b)=1\) then \(\varphi(ab)=\varphi(a)\varphi(b)\).
• For a prime \(p\), \(\varphi(p)=p-1\).
• For a prime power \(p^k\), \(\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)\).

Computing \(\varphi(n)\)

Given the prime factorisation \( n = \prod_{i=1}^{r} p_i^{k_i} \),

\[ \varphi(n)=n\prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right) \]

Example

Compute \(\varphi(36)\).

36 = 2^2 * 3^2
φ(36) = 36 * (1‑1/2) * (1‑1/3) = 36 * 1/2 * 2/3 = 12

Applications

Euler's totient appears in many areas:

• Euler's theorem: \(a^{\varphi(n)}\equiv1\pmod n\) for \(\gcd(a,n)=1\).
• RSA cryptography.
• Counting primitive roots.