Number of multiplicative inverses in $\mathbb{Z}_m$

Question

Is there a formula for the number of multiplicative inverses (invertibles) in $\mathbb{Z}_m$? I know one way would be to count for how many elements $n \in \mathbb{Z}_m$, $0<n<m$ the following equation satisfies: $\gcd (n,m)=1$.

Answer 1

The most common formula is $\phi(m) = m\prod_{p|n;p\ prime}(1-\frac 1p)$ (So, for example, $\phi(24) = 24(1-\frac 12)(1-\frac 13) = 24\cdot \frac 12\cdot \frac23=8$.) But I personally prefer $\phi(\prod p_i^{a_i}) =\prod p_i^{a_i-1}\prod(p_i - 1)$. (So, for example $\phi (24) = \phi(2^3\cdot 3) = (2^2\cdot 3^0)(2-1)(3-1) = 8$.)

These handy rules will never let you down: If $p$ is prime then $\phi(p) = p-1$. And $\phi(p^k) = p^{k-1}(p-1)$. ANd if $\gcd(m,n) = 1$ then $\phi(mn) = \phi(m)\cdot\phi(n)$.

Answer 2

Yes, this is precisely what the Euler totient function $\phi(n)$ counts. It is also easy to compute given a prime factorisation of $n$ as $\phi(p^n)=p^n-p^{n-1}$ for prime $p$, and $\phi$ is multiplicative.