Encuentre un número natural$m$ que es producto de 3 números primos, y que la ecuación$x^2+1 \equiv 0 \text { (mod m)}$ tiene exactamente 4 soluciones mod m.
Respuestas
¿Demasiados anuncios?
Boceto, la mayoría sin prueba, algunos teoría estándar. Deje $m$ primer poder de la factorización de $$m=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}.$$ La congruencia $x^2\equiv -1\pmod{m}$ tiene solución si y sólo si la congruencia $x^2\equiv -1\pmod{p_i^{a_i}}$ tiene solución para todos los $i$.
Por otra parte, vamos a $e_i$ el número de soluciones de la congruencia $x^2\equiv -1\pmod{p_i^{a_i}}$. A continuación, el número de soluciones de $x^2\equiv -1\pmod{m}$$e_1e_2\cdots e_k$.
Brevemente, esto es debido a que dado soluciones $c_i$$x^2\equiv -1\pmod{p_i^{a_i}}$, podemos utilizar el Teorema del Resto Chino para encontrar una solución a $x$ del sistema de congruencias $x\equiv c_i \pmod{p_i^{a_i}}$, y esto va a satisfacer $x^2\equiv -1\pmod{p_i^{a_i}}$.
Hasta ahora no hemos utilizado las propiedades de $x^2+1$ aparte de que es un polinomio. Pero ahora necesitamos examinar la solvencia de $x^2 \equiv -1\pmod{p^a}$.
El primer $2$ es especial. La congruencia $x^2\equiv -1\pmod{2}$ tiene una solución, mientras que para $a\gt 1$, de la congruencia $x^2\equiv -1 \pmod{2^a}$ no tiene soluciones.
Nos dirigimos a los impares, números primos $p$. Se trata de un estándar teorema de que la congruencia $x^2\equiv -1 \pmod{p^a}$ no hay soluciones si $p$ es de la forma $4q+3$, y tiene exactamente dos soluciones si $p$ es de la forma $4q+1$.
Esta información es suficiente para resolver cualquier problema del mismo tipo general como el problema en la OP.
Para ser más específicos, si tenemos $3$ distintos números primos $p_1,p_2,p_3$, e $m=p_1p_2p_3$, entonces la congruencia $x^2\equiv -1\pmod{m}$ $e_1e_2e_3$ soluciones, donde $e_i$ es el número de soluciones de $x^2\equiv -1\pmod{p_i}$. Desde $e_i=1$ si $p_i=2$, e $e_i=0$ o $2$ lo contrario, si $e_1e_2e_3=4$ debemos tener una de las $p_i$ (es decir $p_1$) igual a $2$, y los otros dos deben ser de la forma $4q+1$.
Las primeras posibilidades son $m=(2)(5)(13)$, $m=(2)(5)(17)$, $(2)(5)(29)$, $(2)(5)(37)$, $(2)(5)(41)$, y $(20(13)(17)$.
Por ejemplo, echemos un vistazo a $m=(2)(5)(17)$. Soluciones de $x^2\equiv -1$ modulo los números primos $2, 5,17$ son, respectivamente,$1$, $\pm 2$, $\pm 4$. Así queremos encontrar $x$, lo que es extraño y es congruente a $\pm 2\pmod{5}$, e $\pm 4\pmod{17}$.
Que nos da la $4$ sistemas de congruencias para resolver, usando la maquinaria de la CRT, o por la inspección. Resolvamos por ejemplo, $x$ impar, congruente a $2$ mod $5$, e $-4$ modulo $17$. Una búsqueda rápida de los rendimientos de $x=47$.
Esto demuestra que $-47$ resuelve el problema de $x$ impar, congruente a $-2$ modulo $5$, e $4$ modulo $17$.
Sólo dos más para ir, en realidad sólo uno, ya que podemos cambiar los signos.
Jean-Claude Arbaut
Puntos
9403
