RSA Totient

Euler's totient counts how many numbers below n share no factor with it. When n is a product of two distinct primes the count is easy to reason out: of the $pq$ numbers below n, the multiples of p are q of them and the multiples of q are p of them, with 0 shared. Subtracting gives $pq - p - q + 1$, which factors as $(p-1)(q-1)$. For the textbook key that is $60 \times 52 = 3120$.

φ(n) is what makes the encryption reversible. The private exponent d is chosen so that $ed \equiv 1 \pmod{\varphi(n)}$, and Euler's theorem then guarantees that raising to e and back to d returns the original message. This is also why φ is as secret as the primes themselves — hand someone φ(n) alongside the public n and they can recover p and q immediately, which is what the companion formula on this site does.

Two footnotes worth knowing. Modern implementations usually use the Carmichael function λ(n) = lcm(p−1, q−1) rather than φ, because it gives a smaller valid d and slightly faster decryption; φ still works and is what the original paper specified. And p must differ from q. If they are equal, n = p² and the count is $p(p-1)$, not $(p-1)^2$ — the derivation above assumed the multiples of p and of q were different sets.