Encontrar todas las raíces de $\,x^2\!\equiv x\pmod{\!900}$ es decir, todos los idempotentes en $\Bbb Z_{900}$

Question

Necesito los elementos idempotentes de $Z_{900}$

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

Por supuesto que hay $$0 \pmod 4 \\ 0 \pmod 9 \\ 0 \pmod {25} \\ $$ y $$1 \pmod 4 \\ 1 \pmod 9 \\ 1 \pmod {25} \\ $$

Encontré las respuestas haciendo un programa en C++ para probar todos los números, pero no sé cómo resolver rápidamente en papel.

Esta es la salida del programa $(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

Como has notado, $900$ factores en $2^23^25^2$ y la relevancia de esto es que el Teorema del resto chino nos da un isomorfismo $\Bbb Z_{900}\cong\Bbb Z_{2^2}\times\Bbb Z_{3^2}\times\Bbb Z_{5^2}$ . Se puede demostrar fácilmente que un idempotente de este anillo debe ser de la forma $(e_1,e_2,e_3)$ donde cada uno de los $e_i$ son idempotentes en $\Bbb Z_{p^2}$ . Esto reduce el problema a uno en $\Bbb Z_{p^n}$ y luego, aplicando el teorema del resto chino, se pueden elevar los idempotentes a elementos de $\Bbb Z_{900}$ .

Siguiendo esta estrategia pasamos por varios lemas perspicaces que pueden ser útiles para otros problemas.

Comprender $\Bbb Z_{p^n}$

Por correspondencia ideal, y nuestro conocimiento de los ideales de $\Bbb Z$ los únicos ideales propios de $\Bbb Z_{p^n}$ son de la forma $(p^k+p^n\Bbb Z)$ donde $1\leq k\leq n$ y $(p+p^n\Bbb Z)$ es el único ideal maximal del anillo completo. Eso lo convierte en un principal ideal ¡también! Además, puede ver que $x^n=0+p^n\Bbb Z$ por cada $x\in (p+p^n\Bbb Z)$ es decir, cada elemento que hay nilpotente .

Datos útiles sobre los idempotentes

Si $e$ es un idempotente

1. entonces $1-e$ también es idempotente.
2. entonces $e(1-e)=0$ .
3. y también nilpotente, entonces es cero.

Juntos conseguimos

Por ahora, permítanme dejar el $+p^n\Bbb Z$ en la notación del coset para despojar las matemáticas. Quiero decir que estoy escribiendo $(p)$ en lugar de $(p+p^n\Bbb Z)$ en $\Bbb Z_{p^n}$ .

Dejemos que $e$ sea idempotente en $\Bbb Z_{p^n}$ . Entonces, como $e(1-e)=0\in (p)$ y $(p)$ es primo, uno de $e$ o $1-e$ está en $(p)$ .

Si $e\in (p)$ , entonces es tanto un idempotente como un nilpotente, por tanto cero.

Si en cambio $1-e\in (p)$ Entonces, con el mismo argumento, $1-e=0$ . Pero esto es lo mismo que decir $e=1$ .

Así que en conclusión, se puede ver que el $e_i$ deben ser los elementos cero o los elementos de identidad de sus respectivos anillos. En total eso da $2^3$ opciones de idempotentes, cada una de las cuales se puede retirar para $\Bbb Z_{900}$ a través de tu implementación favorita del teorema del resto chino.

Answer 2

Sugerencia $\ \,p\,$ de primera, $\,p^n\mid e(1\!-\!e)\,\Rightarrow\, p^n\mid e\,$ o $\,p^n\mid 1\!-\!e,\ $ por $\ 1\!-\!e,\, e\,$ coprima, por $\ (1\!-\!e)+ e = 1$

Así, los únicos idempotentes mod $\,p^n\,$ son los idempotentes triviales $\,e \equiv 0,1.\,$

Entonces, por CRT, $\,e\,$ es idempotente mod $\,2^2 3^2 5^2\iff e \equiv 0,1\,$ mod $\,2^2,3^2,5^2,\,$ Por ejemplo

$\ 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,\,$ así que $\, e = 15^2k = 15^2(1\! +\! 4j)\equiv 225\pmod{\!900}$

Así que $\,(0,1,1) = 1-e \equiv 1-225 = 901-225 \equiv 676.\,$ Lo mismo para otros $\,(e_1,e_2,e_2),\ e_i \in \{0,1\}$

Nota: $\ $ Idempotentes $\!\bmod n\,$ corresponden a escisiones de $n$ en $\color{#c00}{\rm co}\color{#0a0}{\rm prime}$ factores, por ejemplo, por encima del idempotente $\,e = 225 = 3^2 5^2\,$ corresponde a la factorización $\,n = \color{#c00}{2^2}\!\times \color{#0a0}{3^2 5^2}\,$ donde $\,\color{#c00}{e\equiv 1\pmod{\!2^2}},\,$ $\color{#0a0}{e\equiv 0\pmod{\!3^2 5^2}}.\,$ De hecho, algunos algoritmos de factorización de enteros funcionan buscando idempotentes no triviales mod $\,n,\,$ que inmediatamente dan una factorización de $\,n\,$ ( por lo general, podemos factorizar rápidamente $\,n\,$ dado cualquier polinomio que tenga más raíces mod $\,n\,$ que su grado, por lo que un idempotente no trivial (o raíz cuadrada) $\Rightarrow$ cuadrática tiene $> 2$ raíces, que divide $n$ ).

Generalmente podemos encontrar raíces modulares de polinomios utilizando la TRC como se explica a continuación, donde lo anterior es el caso especial $f(x) = x^2 -x = x(x-1)$ .

Por CRT, cada combinación de una raíz $\,r_i\,$ mod $\,m\,$ y una raíz $\,s_j\,$ mod $\,n\,$ corresponde a una única raíz $\,t_{ij}\,$ mod $\,mn\,$ es decir

$$\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$$

Algunos algoritmos de factorización de enteros funcionan buscando idempotentes no triviales mod $\,n,\,$ que inmediatamente dan una factorización de $\,n\,$ ( por lo general, uno puede factorizar rápidamente $\,n\,$ dado cualquier polinomio que tenga más raíces mod $\,n\,$ que su grado, por lo que cualquier idempotente no trivial o raíz cuadrada no trivial dividirá $\,n,\,$ ya que da lugar a una cuadrática con $3$ raíces).