La pregunta es la siguiente: utilice la TRC para demostrar que si un número entero $n>1$ no es una potencia de un primo, entonces existe un número entero $x$ tal que $n|(x^{2}-x)$ pero $n$ no divide $x$ ni $x-1$ . Puedo ver que esto funciona con un ejemplo simple como $n=12$ que permite $x=4,-3$ . Lo conseguí utilizando $n|(x^{2}-x)$ para dar a entender $x^{2}-x-nk=0$ pero no puedo ver para probar esto con el CRT en particular. Se agradece cualquier ayuda.
Respuestas
¿Demasiados anuncios?
Oli
Puntos
89
Supongamos que $n$ no es una potencia primera. Entonces $n=ab$ para algunos relativamente primera números $a$ y $b$ , ambos mayores que $1$ .
Por el Teorema del Resto Chino, existe un número entero $x$ tal que $x\equiv 0\pmod{a}$ y $x\equiv 1\pmod{b}$ . Así, $a$ divide $x$ y $b$ divide $x-1$ . De ello se desprende que $ab$ divide $x(x-1)$ . Tenga en cuenta que $ab$ no divide $x$ , para $b$ divide $x-1$ y por lo tanto $b$ y $x$ son relativamente primos. Del mismo modo, se puede demostrar que $ab$ no divide $x-1$ .
David HAust
Puntos
2696
Sugerencia $\bmod n\,$ buscamos una solución de $\ x(x-1)\equiv 0\ $ pero $\,x\not\equiv 0,1.\, $ Si $\,n = p^k\,$ es una potencia prima obtenemos sólo soluciones triviales: $\,p^k\mid x(x-1)\,$ $\Rightarrow\,p^k\mid x\,$ o $\,p^k\mid x-1\,$ por $\,x,\,$ $\,x-1\,$ coprime. Si no $\,n\,$ no es una potencia primera, por lo que podemos escribir $\,n = ab\ $ con coprima $\,a,b>1.\,$ Qué pasa cuando levantamos las soluciones de CRT $\, x\equiv 0,1\,$ mod $\,a,b\,$ a cuatro soluciones mod. $\,n\,?$ Las soluciones $\,x\equiv (0,0),(1,1)\,$ mod $\,(a,b)\,$ mapa a $0,1\,$ mod $ab,\,$ pero las soluciones $\,(0,1),(1,0)\,$ mod $\,(a,b)\,$ mapa de valores $\not\equiv 0,1\,$ mod $\,ab.$
Nota: $\ $ Elementos satisfactorios $\,x^2 = x\,$ (y $\,\color{#c00}{x\neq 0,1})$ se llaman $\rm\color{#c00}{(nontrivial)}$ idempotentes . Son íntimamente ligado a las factorizaciones coprimas (tanto de elementos como de anillos). Como vemos arriba, modulo cualquier compuesto no primo-potente $\,n,\,$ hay idempotentes no triviales $\,(0,1),(1,0).$
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).
