What is Euler's phi function $\varphi(n)$, and what are the rules for computing it?

Question

Accepted Answer

$\varphi(n)$ counts how many integers from 1 to n are coprime with n (i.e., $\gcd(a, n) = 1$). It's essential for RSA key generation.
Definition: $\varphi(n) = |\{a \in \mathbb{N} : 1 \leq a < n, \gcd(a, n) = 1\}|$
Three computation rules:
Rule 1 — Prime: $\varphi(p) = p - 1$

Example: $\varphi(11) = 10$ (all of 1-10 are coprime with 11)

Rule 2 — Product of coprimes: $\varphi(n \cdot m) = \varphi(n) \cdot \varphi(m)$ when $\gcd(n, m) = 1$

Example: $\varphi(30) = \varphi(2 \cdot 3 \cdot 5) = \varphi(2) \cdot \varphi(3) \cdot \varphi(5) = 1 \cdot 2 \cdot 4 = 8$
Warning: $25 = 5 \cdot 5$, but $\varphi(25) = 20 
eq \varphi(5) \cdot \varphi(5) = 16$ — because $\gcd(5, 5) 
eq 1$!

Rule 3 — Prime power: $\varphi(p^k) = p^k - p^{k-1} = p^k(1 - \frac{1}{p})$

Example: $\varphi(27) = \varphi(3^3) = 27 - 9 = 18$
Example: $\varphi(25) = \varphi(5^2) = 25 - 5 = 20$

For RSA ($N = p \cdot q$ with distinct primes):
$$\varphi(N) = \varphi(p \cdot q) = (p-1)(q-1)$$
This is the formula used in RSA key generation — and it can only be computed if you know the factorization of N (the trapdoor!).
Go deeper:

Euler's totient function (Wikipedia) — all the computation rules and their proofs.
 RSA: generating the keys (Eddie Woo) — how φ(N) drives RSA key generation.