Find all roots of $\,x^2\!\equiv x\pmod{\!900}$, i.e all idempotents in $\Bbb Z_{900}$

Question

I need the idempotent elements of $Z_{900}$

$2^2\cdot 3^2\cdot 5^2=900$

Of course there's $$0 \pmod 4 \\ 0 \pmod 9 \\ 0 \pmod {25} \\ $$ and $$ 1 \pmod 4 \\ 1 \pmod 9 \\ 1 \pmod {25} \\ $$

I found the answers by making a C++ program to test all numbers, but I don't know how to quick solve on paper.

This is the output of the program $(0, 0, 0) \rightarrow 0 \\ (1, 1, 1) \rightarrow 1 \\ (0, 0, 1) \rightarrow 576 \\ (0, 1, 0) \rightarrow 100 \\ (1, 0, 0) \rightarrow 225 \\ (1, 1, 0) \rightarrow 325 \\ (0, 1, 1) \rightarrow 676 \\ (1, 0, 1) \rightarrow 801 \\$

Answer 1

Hint $\ \,p\,$ prime, $\,p^n\mid e(1\!-\!e)\,\Rightarrow\, p^n\mid e\,$ or $\,p^n\mid 1\!-\!e,\ $ by $\ 1\!-\!e,\, e\,$ coprime, by $\ (1\!-\!e)+ e = 1$

So $\!\bmod p^n$ the only idempotents (roots of $\,e^2\equiv e)\,$ are the trivial idempotents $\,e \equiv 0,1.\,$

So, by CRT [cf, below] $\,e\,$ is idempotent mod $\,2^2 3^2 5^2\iff e \equiv 0,1\,$ mod $\,2^2,3^2,5^2,\,$ e.g.

$\ e \equiv (\color{#c00}1,0,0)\Rightarrow {\rm mod}\ 2^2\!:\ e\equiv \color{#c00}1 \equiv 3^2 5^2 k \equiv \color{#c00}k,\,$ so $\, e = 15^2k = 15^2(1\! +\! 4j)\equiv 225\pmod{\!900}$

So $\,(0,1,1) = 1-e \equiv 1-225 = 901-225 \equiv 676.\,$ Same for other $\,(e_1,e_2,e_2),\ e_i \in \{0,1\}$

Remark $\ $ Idempotents $\!\bmod n\,$ correspond to splittings of $n$ into $\color{#c00}{\rm co}\color{#0a0}{\rm prime}$ factors, e.g. above the idempotent $\,e = 225 = 3^2 5^2\,$ corresponds to the factorization $\,n = \color{#c00}{2^2}\!\times \color{#0a0}{3^2 5^2}\,$ where $\,\color{#c00}{e\equiv 1\pmod{\!2^2}},\,$ $\color{#0a0}{e\equiv 0\pmod{\!3^2 5^2}}.\,$ In fact some integer factorization algorithms work by searching for nontrivial idempotents mod $\,n,\,$ which immediately yield a factorization of $\,n\,$ (generally we can quickly factor $\,n\,$ given any polynomial which has more roots mod $\,n\,$ than its degree, so a nontrivial idempotent (or square-root) $\Rightarrow$ quadratic has $> 2$ roots, which splits $n$).

Generally we can find modular roots of polynomials using CRT as explained below, where above is the special case $f(x) = x^2 -x = x(x-1)$.

By CRT, each combination of a root $\,r_i\,$ mod $\,m\,$ and a root $\,s_j\,$ mod $\,n\,$ corresponds to a unique root $\,t_{ij}\,$ mod $\,mn\,$ i.e.

$$\begin{eqnarray} f(x)\equiv 0\pmod{mn}&\overset{\rm CRT}\iff& \begin{array}{}f(x)\equiv 0\pmod m\\f(x)\equiv 0\pmod n\end{array} \\ &\iff& \begin{array}{}x\equiv r_1,\ldots,r_k\pmod m\phantom{I^{I^{I^I}}}\\x\equiv s_1,\ldots,s_\ell\pmod n\end{array}\\ &\iff& \left\{ \begin{array}{}x\equiv r_i\pmod m\\x\equiv s_j\pmod n\end{array} \right\}_{\begin{array}{}1\le i\le k\\ 1\le j\le\ell\end{array}}^{\phantom{I^{I^{I^I}}}}\\ &\overset{\rm CRT}\iff& \left\{ x\equiv t_{i j}\!\!\pmod{mn} \right\}_{\begin{array}{}1\le i\le k\\ 1\le j\le\ell\end{array}}\\ \end{eqnarray}\qquad\qquad$$

Answer 2

As you noticed, $900$ factors into $2^23^25^2$, and the relevance of this is that the Chinese remainder theorem gives us an isomorphism $\Bbb Z_{900}\cong\Bbb Z_{2^2}\times\Bbb Z_{3^2}\times\Bbb Z_{5^2}$. You can easily show that an idempotent of this ring must be of the form $(e_1,e_2,e_3)$ where each of the $e_i$ are idempotent in $\Bbb Z_{p^2}$. This reduces the problem to one in $\Bbb Z_{p^n}$, and then by implementing the Chinese remainder theorem you can lift the idempotents back to elements of $\Bbb Z_{900}$.

Following this strategy takes us past several insightful lemmas that can come in handy for other problems.

Understand $\Bbb Z_{p^n}$

By ideal correspondence, and our knowledge of ideals of $\Bbb Z$, the only proper ideals of $\Bbb Z_{p^n}$ are of the form $(p^k+p^n\Bbb Z)$ where $1\leq k\leq n$, and $(p+p^n\Bbb Z)$ is the unique maximal ideal of the whole ring. That makes it a prime ideal as well! Furthermore, you can see that $x^n=0+p^n\Bbb Z$ for every $x\in (p+p^n\Bbb Z)$, that is, every element there is nilpotent.

Useful facts about idempotents

If $e$ is an idempotent

1. then $1-e$ is idempotent too.
2. then $e(1-e)=0$.
3. and also nilpotent, then it is zero.

Together we get

For now, let me drop the $+p^n\Bbb Z$ in the coset notation to declutter the math. I mean that I'm writing $(p)$ rather than $(p+p^n\Bbb Z)$ in $\Bbb Z_{p^n}$.

Let $e$ be idempotent in $\Bbb Z_{p^n}$. Then since $e(1-e)=0\in (p)$ and $(p)$ is prime, one of $e$ or $1-e$ is in $(p)$.

If $e\in (p)$, then it's both an idempotent and a nilpotent, hence zero.

If instead $1-e\in (p)$, then by the same argument, $1-e=0$. But this is the same as saying $e=1$.

So in conclusion, you can see that the $e_i$ must be either the zero elements or the identity elements of their respective rings. In total that gives you $2^3$ choices of idempotents, each of which you can pull back to $\Bbb Z_{900}$ via your favorite implementation of the Chinese remainder theorem.