How many idempotent elements does the ring ${\bf Z}_n$ contain?

Let $R$ be a ring. An element $x$ in $R$ is said to be idempotent if $x^2=x$. For a specific $n\in{\bf Z}_+$ which is not very large, say, $n=20$, one can calculate one by one to find that there are four idempotent elements: $x=0,1,5,16$. So here is my question:

Is there a general result which tells the number of the idempotent elements of ${\bf Z}_n$?


If $n=p_1^{m_1}\cdots p_k^{m_k}$ is the factorization of $n$ as a product of powers of distinct primes, then the ring $\mathbb Z/n\mathbb Z$ is isomorphic to the product $\mathbb Z/p_1^{m_1}\mathbb Z\times\cdots\times \mathbb Z/p_k^{m_k}\mathbb Z$. It is easy to reduce the problem of counting idempotent elements in this direct product to counting them in each factor.

Can you do that?


In $\Bbb{Z}_n$ the relation $x^2=x$ is equivalent to $(x-1)x\equiv 0 ( mod \ n)$, that is $n | x(x-1)$. This is an easy way to calculate all idempotent elements for small $n$. In general, you need to consider the factorization of $n$ in prime factors and note that $x,x-1$ are coprime, and if one prime number divides one of them, it can't divide the other.


Hint $ $ Idempotents in $\,\mathbb Z/n\,$ correspond to coprime factorizations of $\,n\,$ i.e. $\, n = a\,b,\ (a,b) = 1\,.\ $ Indeed, notice that $\,p^k\mid\,(e-1)\iff p^k\ |\ e\,$ or $\,p^k\ |\ e-1.\,$ It is easy to see that there are $\, 2^k\,$ such factorizations, where $\,k\,$ is the number of distinct prime factors of $\, n.$