Mejor respuesta
Diga, 2 ^ 32 + 1 es divisible entre m.
Entonces, 2 ^ 32 = -1 (mod m)
(2 ^ 32) ^ 3 = (- 1) ^ 3 ( mod m)
2 ^ 96 = -1 (mod m)
2 ^ 96 + 1 = 0 (mod m)
Entonces, la respuesta correcta es 2 ^ 96 + 1
Respuesta
No es así. Por ejemplo, mira lo que sucede cuando x = 12. Obtienes x ^ 2 = 144 = 24 \ cdot 6 pero x no es divisible por 24.
Podría detenerme aquí, pero eso no sería instructivo , excepto para decir que estás equivocado. Eso no es particularmente útil.
Después de todo, puedo demostrar que si k | x ^ 2 (lea eso como “k divide x ^ 2), entonces k | x para muchos k, incluidos 21, 22, 23, 26, 29 y 30, pero no para 20, 24, 25, 27 o 28. ¿Cuál es la diferencia? Ahí es donde las cosas se ponen interesantes e instructivas.
¿Qué sabemos sobre x? Sabemos, por el Teorema fundamental de la aritmética, que x se puede representar de forma única como un producto de números primos, x = 2 ^ {a\_2} 3 ^ {a\_3} 5 ^ {a\_5} \ cdots. Cualquiera (o todos, para x = 1) de esos valores a\_p podrían ser 0 y, de hecho, solo un número finito de ellos son distintos de cero.
Eso significa que x ^ 2 = 2 ^ { 2a\_2} 3 ^ {2a\_3} 5 ^ {2a\_5} \ cdots. Todos los exponentes ahora son pares.
¿Qué sabemos sobre k? Por el mismo teorema, sabemos que k = 2 ^ {k\_2} 3 ^ {k\_3} 5 ^ {k\_5} \ cdots.
¿Cómo se relaciona esto con la divisibilidad? Si k | x ^ 2, eso significa que k\_2 \ leq 2a\_2, k\_3 \ leq 2a\_3, \ dots, k\_p \ leq 2a\_p, \ dots. Sin embargo, si k | x, eso significa que k\_2 \ leq a\_2, k\_3 \ leq a\_3, \ dots, k\_p \ leq a\_p.
Entonces, todo lo que tenemos que hacer realmente para demostrar si x ^ 2 es divisible por k, entonces x es divisible por k muestra que si k\_p \ leq 2a\_p, entonces k\_p \ leq a\_p. Dado que k\_p, a\_p puede ser cualquier número entero no negativo, entonces podemos ver el problema más simple: ¿bajo qué condiciones tenemos b \ leq 2c implicando b \ leq c?
Básicamente, estamos tratando de encontrar valores de b donde la expresión c \ leq 2c no es válida para ningún c. Dado que no hay c , entonces b = 0 funciona. Para b = 1, estamos obligados a tener c = 0 , por lo que 1 \ not \ leq 2c = 0, entonces b = 1 funciona.
Pero para b> 1, no trabajo. Siempre puedes elegir c = b-1
Para traer esto de vuelta a nuestro problema, eso significa que podemos decir k | x ^ 2 \ implica k | x solo cuando los exponentes de los números primos en k son 0 o 1. Estos valores de k se denominan «libres de cuadrados» porque no puedes dividirlos por un número cuadrado.
Entonces puedes mostrar k | x ^ 2 \ implica k | x si k no tiene ningún cuadrado.
Para los números que miré arriba, 20 es divisible por el cuadrado 4, 24 es divisible por el cuadrado 4, 25 es cuadrado, 27 es divisible por el cuadrado 9 , 28 es divisible por el cuadrado 4. Los otros números, 21, 22, 23, 26, 29, 30, son todos libres de cuadrados, que puede comprobar si lo desea.