¿Puedes mostrar cómo resolver la congruencia x ^ 2equiv 6 (mod 15) sin usar el teorema del resto chino?

¿Puedes mostrar cómo resolver la congruencia x ^ 2equiv 6 (mod 15) sin usar el teorema del resto chino?

Permítanme comenzar recomendando la respuesta de Dean Rubine a esta pregunta, y luego desarrollaré su enfoque general.

Como Dean mencionó, 15 es un número bajo agradable, por lo que podemos echar un vistazo completo a todos los cuadrados (llamados residuos cuadráticos) (mod 15).

Lo primero que vale la pena señalar es que los cuadrados de [matemáticas] a [/ matemáticas] y [matemáticas] -a [/ matemáticas] son iguales. Esto es cierto tanto para la aritmética ordinaria como para la aritmética modular. Entonces, si bien es natural enumerar los residuos (mod 15) como 0 a 14, podemos facilitarnos las cosas enumerándolos como -7 a 7. Estos residuos simplemente representan la clase de residuo a la que pertenecen, por lo que no No importa qué representante use.

Así que aquí hay una tabla compacta de los residuos (mod 15) y sus cuadrados:

[matemáticas] \ qquad \ begin {align} \ textbf {mod} & \ textbf {15} \\\ hline ~ \\ 0 ^ 2 & \ equiv 0 \\ (\ pm 1) ^ 2 & \ equiv 1 \\ (\ pm 2) ^ 2 & \ equiv 4 \\ (\ pm 3) ^ 2 & \ equiv -6 \\ (\ pm 4) ^ 2 & \ equiv 1 \\ (\ pm 5) ^ 2 & \ equiv -5 \\ (\ pm 6) ^ 2 & \ equiv 6 \\ (\ pm 7) ^ 2 & \ equiv 4 \ end {align} [/ math]

Entonces los cuadrados (mod 15) son [matemática] -6, -5, 0, 1, 4, 6, [/ matemática] y las dos raíces cuadradas de [matemática] 6 [/ matemática] son [matemática] \ pm 6 , [/ math] que es equivalente a la respuesta de Dean.

Hay otra forma de abordar este problema. A riesgo de virar demasiado cerca del Teorema del resto chino, señalaré que [matemáticas] 6 [/ matemáticas] y [matemáticas] 15 [/ matemáticas] comparten un factor común, [matemáticas] 3. [/ Matemáticas] Si [math] x ^ 2 \ equiv 6 [/ math] (mod 15) entonces [math] x ^ 2 \ equiv 1 [/ math] (mod 5), y es aún más fácil trabajar en mod 5 que mod 15, no solo porque 5 es menor que 15, sino también porque 5 es primo, por lo que puede estar seguro de que hay como máximo dos raíces cuadradas de cualquier residuo.

[matemáticas] \ qquad \ begin {align} \ textbf {mod} & \ textbf {5} \\\ hline ~ \\ 0 ^ 2 & \ equiv 0 \\ (\ pm 1) ^ 2 & \ equiv 1 \\ (\ pm 2) ^ 2 & \ equiv -1 \ end {align} [/ math]

Entonces, las dos raíces cuadradas de [math] 1 [/ math] son [math] x \ equiv \ pm 1 [/ math] (mod 5), y como sabemos que x es un múltiplo de 3, x debe ser equivalente a [ matemáticas] \ pm 6 [/ matemáticas] (mod 15).