Idempotents in $\mathbb Z_n$ An element $a$ of the ring $(P,+,\cdot)$ is called idempotent if $a^2=a$. An idempotent $a$ is called nontrivial if $a \neq 0$ and $a \neq 1$. 
My question concerns idempotents in rings $\mathbb Z_n$, with addition and multiplication modulo $n$, where $n$ is natural number. Obviously when $n$ is a prime number then there is no nontrivial idempotent. If $n$ is nonprime it may happen, for example $n=4, n=9$, that also there is no.

Is it known, in general, for what $n$ there are nontrivial idempotents and what is a form of such idempotents?

 A: A start: You can figure it out! Let us start with a product $mn$ of relatively prime integers, neither equal to $1$. By the Chinese Remainder Theorem, there is an $x$ such that $x\equiv 0\pmod{m}$ and $x\equiv 1 \pmod{n}$. Then $x^2\equiv x \pmod{mn}$. 
Generalize to a product of $k$ relatively prime integers. If you use the prime power factorization, you can get a complete list.
A: By the Chinese remainder theorem $\mathbf Z/n\mathbf Z$ is a product of more than one (unital) ring if and only if $n$ has more than one prime factor, and in this case $\mathbf Z/n\mathbf Z$ certainly has nontrivial idempotents. If on the other hand $n=p^k$ is a prime power, then all elements are either invertible (if not divisible by $p$) or nilpotent (if divisible by $p$) and this excludes the possibility of nontrivial idempotents. The case $n=1$ is a special case of a prime power (but the unique element now is both invertible and nilpotent; there are still no nontrivial idempotents of course).
A: As often happens when dealing with $\mathbf{Z}_n$, the Chinese remainder theorem is your friend. If the prime factorization of $n$ is
$$
n=\prod_i p_i^{a_i},
$$
then by CRT we have an isomorphism of rings
$$
\mathbf{Z}_n\cong\bigoplus_i \mathbf{Z}_{p_i^{a_i}}.
$$
Observe that the isomorphism maps the residue class of an integer $m$ (modulo $n$) to a vector with all the components equal to the residue class of $m$ (this time modulo various prime powers):
$$
\overline{m}\mapsto(\overline{m},\overline{m},\ldots,\overline{m}).
$$
So the residue class of $m$ is an idempotent if and only if it is an idempotent modulo all the
prime powers $p_i^{a_i}$. 
Let us look at the case of a prime power modulus $p^t$. The congruence $x^2\equiv x\pmod{p^t}$ holds, iff $p^t$ divides $x^2-x=x(x-1)$.
Here only one of the factors of, $x$ or $(x-1)$, can be divisible by $p$, so for the
product to be divisible by $p^t$ the said factor then has to be divisible by $p^t$. Thus we can conclude that $x\equiv 0,1 \pmod{p^t}$ are the only idempotents modulo $p^t$.
Therefore we require that
$$
m\equiv 0,1\pmod{p_i^{a_i}}
$$
for all $i$. By CRT these congruences are independent for different $i$, so the number of pairwise non-congruent idempotents is equal to $2^\ell$, where $\ell$ is the number of distinct prime factors $p_i$ of $n$.
A: Let $m=p^{c_{1}}_{1}...p^{c_{n}}_{n}$ be a prime factorization of an integer $m$ with $c_{i}\geq1$ and $p_{i}$ are distinct prime numbers. Then the ring $\mathbb{Z}/m\mathbb{Z}$ has $2^{n}$ idempotents and (modulo $m$) these are precisely of the form $\sum\limits_{k=1}^{n}h_{k}\epsilon_{k}$ where $\epsilon_{k}\in\{0,1\}$ and $h_{k}\in\left(\prod\limits_{\substack{i=1,\\
i\neq k}}^{n}p^{c_{i}}_{i}\right)\mathbb{Z}$ such that $h_{k}-1\in p^{c_{k}}_{k}\mathbb{Z}$.
A: Hint $ $ Globally, idempotents in $\:\Bbb Z_{ n}\:$ correspond to factorizations of $\:n\:$ into two coprime factors, i.e. if $\:e^2 = e\in\Bbb Z_n\:$ then $\:n\:|\:e(e\!-\!1)\:$ thus $\:n = jk,\ j\:|\:e,\ k\:|\:e\!-\!1,\:$ so $\:(j,k)= 1\:$ by $\:(e,e\!-\!1) = 1.\:$ Conversely if $\:n = jk\:$ for $\:(j,k)= 1,\:$ then by CRT, $\:\Bbb Z_n\cong \Bbb Z_j\times \Bbb Z_k\:$ which has nontrivial idempotents $\:(0,1),\,(1,0).\:$ It is rather easy to further explicitly describe this correspondence.  Some integer factorization algorithms search for such nontrivial idempotents.
This correspondence between idempotents and factorizations holds more generally at the structural level - see the Peirce Decomposition. and this answer.
