Encuentra todos los enteros positivos $x$ tal que $13 \mid (x^2 + 1)$

Question

Yo era capaz de resolver esto de la mano para obtener $x = 5$$x =8$. Yo no sé si hay más soluciones, por lo que sólo verificado por WolframAlpha. Establezco la relación de congruencia $x^2 \equiv -1 \mod13$ y sólo, literalmente, simplemente multiplica. Esto me lleva a dos preguntas:

1. Pero me preguntaba, ¿cómo puedo hacer esto si $x$'s fueron realmente grandes? No parece multiplicarse por un lado podría ser el único método posible.

2. Además, lo que si hay 15 o 100 $x$'s? ¿Cómo puedo saber cuándo parar?

Answer 1

Si $p$ es una extraña prime, y $a$ no es divisible por $p$, entonces la congruencia $x^2\equiv a\pmod{p}$ $0$ o $2$ soluciones modulo $p$. Se han encontrado dos soluciones incongruentes. Así que tiene todas ellas: todas las soluciones son de la forma $x=5+13k$ o $x=8+13k$ donde $k$ rangos de los números enteros.

En realidad, la búsqueda de una solución sería suficiente, por si $x$ es una solución, automáticamente lo es $-x$.

Para el prime $p$, hay buenos algoritmos para calcular las soluciones de $x^2\equiv a \pmod{p}$, que son factibles incluso para un enorme $p$.

Si el módulo no es primo, las cosas se ponen más complicadas. Supongamos que $m$ es un extraño número $\gt 1$. Deje que el número de los distintos primer divisores de $m$$e$. Entonces la congruencia $x^2\equiv a\pmod{m}$ donde $a$ $m$ son relativamente primos, ha $0$ soluciones o $2^e$ soluciones.

La búsqueda de soluciones puede ser computacionalmente difícil. Si $m$ es el producto de dos números primos, entonces la búsqueda de soluciones es esencialmente equivalente a la factorización $m$. Se cree que esto es en general computionally muy difícil para un enorme $m$.

Answer 2

Comenzando con $2,$ el mínimo número natural $>1$ co-prime con $13,$

$2^1=2,2^2=4,2^3=8,2^4=16\equiv3,2^5=32\equiv6,2^6=64\equiv-1\pmod{13}$

Como $2^6=(2^3)^2,$ $2^3=8$ es una solución de $x^2\equiv-1\pmod{13}$

Ahora, observa que el $x^2\equiv a\pmod m\iff (-x)^2\equiv a$

Por eso, $8^2\equiv-1\pmod {13}\iff(-8)^2\equiv-1$

Ahora, $-8\equiv5\pmod{13}$

---

Si necesitamos $x^2\equiv-1\pmod m$ donde integer $m=\prod p_i^{r_i}$ donde $p_i$s son distintos de los números primos y $p_i\equiv1\pmod 4$ por cada $i$ (Prueba)

$\implies x^2\equiv-1\pmod {p_i^{r_i}}$

Aplicando logaritmo Discreto con respecto a cualquier raíz primitiva $g\pmod {p_i^{r_i}},$

$2ind_gx\equiv \frac{\phi(p_i^{r_i})}2 \pmod {\phi(p_i^{r_i})}$

como si $y\equiv-1\pmod {p_i^{r_i}}\implies y^2\equiv1 $ $\implies 2ind_gy\equiv0 \pmod {\phi(p_i^{r_i})}\implies ind_gy\equiv \frac{\phi(p_i^{r_i})}2 \pmod {\phi(p_i^{r_i})}$ $y\not\equiv0\pmod { {\phi(p_i^{r_i})}}$

Ahora aplicar CRT, relativamente primer módulos de $p_i^{r_i}$

Por ejemplo, si $m=13, \phi(13)=12$ $2$ es una raíz primitiva de $13$

Por eso, $2ind_2x\equiv 6\pmod {12}\implies ind_2x=3\pmod 6$

$\implies x=2^3\equiv8\pmod{13}$ $x=2^9=2^6\cdot2^3\equiv(-1)8\equiv-8\equiv5\pmod{13}$

Answer 3

Podemos hacer este evitando la maquinaria de la congruencia, aunque es esencialmente la misma idea. Deje x = 13a + b, donde 0 < = b < = 12. Entonces x ^ 2 + 1 = 169a ^ 26ab + 2 + b ^ 2 +1.You sólo es necesario encontrar los valores de b tal que b ^ 2 + 1 es divisible por 13 esto es una muestra muy pequeña, como se encuentra que b = 5 o =8.Then b x = 13a + 5 o x = 13a + 8 y tiene infinitamente muchas respuestas. Gris de Edwin