Number of primitive characters modulo $m$.

Question

Let $N(m)$ be the number of primitive Dirichlet characters modulo $m$. Could someone please explain me why it satisfies the following relation?: $$ \phi(m) = \sum_{d|m} N(d). $$

Thank you very much!

Here, $\phi$ is the Euler totient function.

Answer 1

Hint (maybe not the best solution)

First you can prove that if $\gcd(m1,m2)=1$ then $N(m_1m_2)=N(m_1)N(m_2)$ and if $p$ is a prime then $N(p)=p−2$ and $N(p^r)=(p−1)^2p^{r−2}$. So you can first prove the statement for powers of primes, and complete the proof using the miltiplicativity of $N$.

Let me know if you succeeded