Euler's totient calculator

How it works

Euler’s totient $\varphi(n)$ counts the numbers $1 \le k \le n$ with $\gcd(k, n) = 1$, which is the number of elements of the group $\mathbb Z_n^*$ of invertible residues. For a prime, $\varphi(p) = p - 1$.

$\varphi$ is multiplicative ($\varphi(mn) = \varphi(m)\varphi(n)$ when $\gcd(m, n) = 1$), and for a prime power $\varphi(p^e) = p^{e-1}(p - 1)$, since exactly the multiples of $p$ are lost. So from the factorization $\varphi(n) = n \prod_{p \mid n} (1 - 1/p)$. Without the factorization no efficient method is known.

Euler’s theorem says $a^{\varphi(n)} \equiv 1 \pmod n$ for every $a$ coprime to $n$. This is why RSA works: with $N = pq$ and $e d \equiv 1 \pmod{\varphi(N)}$, where $\varphi(N) = (p-1)(q-1)$, raising to $e$ and then to $d$ gives back the message.