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 idempotens 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 happens, 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?

• They certainly do occur: $n=6,a=3.$ – Andrew Jul 27 '12 at 19:07
• There is a nontrivial idempotent in $\mathbb{Z}_n$ if and only if there is $1<a<n$ such that $n\, |\, a(a-1)$. This is because $a^2 \equiv a \pmod n \Leftrightarrow a^2-a \equiv 0 \pmod n$. I'm not entirely sure where you can go with this though! – Clive Newstead Jul 27 '12 at 19:14
• @CliveNewstead Since $a$ and $a-1$ are relatively prime, you get that such $a$ exists if and only if $n$ has two relatively prime nontrivial divisors, and this is equivalent to $n$ having two distinct primes... – N. S. Jul 27 '12 at 19:31

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 congruence 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$.

• Can you please explain why $m\equiv 0,1\pmod{p_i^{a_i}}$ ? I understood everything up till that point – Belgi Jul 28 '12 at 0:55
• @Belgi, the notation was somewhat inconsistent, and the logic a bit of patchwork. Is it clearer now? – Jyrki Lahtonen Jul 28 '12 at 4:48
• What is "m"? ... – Stephen Mar 12 '15 at 19:32
• @Stephen: An integer. More precisely, an integer such that its residue class is an idempotent as explained on the sixth line. – Jyrki Lahtonen Mar 12 '15 at 19:35
• Sorry about the bump. I was reviewing some of my old answers and felt that this could be made a lot clearer (particular in view of Stephen's comment). Hopefully I succeeded. – Jyrki Lahtonen Aug 24 '18 at 9:51

Hint  Idempotents in $$\:\Bbb Z_{ n}\:$$ correspond to factorizations of $$\:n\:$$ into two coprime factors. Namely, 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 not that difficult to explicitly work out the details of the 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.

• It's worth noting here that if $x$ is an idempotent corresponding to a given $j$ and $k$, then $(p+)1-x$ is the other one, so it suffices to compute the idempotent corresponding to either $(0,1)$ or $(1,0)$. – rogerl May 29 '15 at 15:17
• @rogerl Yes that is clear since $\,(0,1)+(1,0) = (1,1) = 1\ \$ – Bill Dubuque Jun 14 '15 at 20:54

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 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.

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 each one is precisely of the form $\sum\limits_{k=1}^{n}h_{k}\epsilon_{k}+m\mathbb{Z}$ where $\epsilon_{k}\in\{0,1\}$ and $h_{k}\in(\prod\limits_{\substack{i=1,\\ i\neq k}}^{n}p^{c_{i}}_{i})\mathbb{Z}$ such that $h_{k}-1\in p^{c_{k}}_{k}\mathbb{Z}$.