Cómo demostrar que 41 divide 2 ^ (20) -1

[matemáticas] \ begin {align}
2 ^ {20} & = 1 \, 048 \, 576 \\
2 ^ {20} -1 & = 1 \, 048 \, 575 \\
1 \, 048 \, 575 & = 3 \ times349 \, 525 \\
349 \, 525 & = 5 \ times69 \, 905 \\
69 \, 905 & = 5 \ times13 \, 981 \\
13 \, 981 & = 11 \ times1 \, 271 \\
1 \, 271 & = 31 \ times41
\ end {align} [/ math]

Entonces [matemáticas] 2 ^ {20} -1 = 3 \ veces5 ^ 2 \ veces1 \ veces31 \ veces41 [/ matemáticas], es divisible por [matemáticas] 41 [/ matemáticas].

También podría haber usado propiedades como [matemáticas] a ^ nb ^ n = (ab) (a ^ {n-1} + a ^ {n-2} b + \ cdots + ab ^ {n-2} + b ^ {n-1}) [/ math] y [math] a ^ n + b ^ n = (a + b) (a ^ {n-1} -a ^ {n-2} b + \ cdots-ab ^ {n-2} + b ^ {n-1}) [/ matemática], para obtener esa [matemática] (2 ^ {8} -2 ^ {6} + 2 ^ {4} -2 ^ {2} + 1) = 205 [/ math] divide [math] 2 ^ {20} -1 [/ math], pero ya sabía cuánto era [math] 2 ^ {20} [/ math].

[matemáticas] (2 ^ {20} -1) \ mod41 [/ matemáticas]

[matemáticas] = (2 ^ {10} -1) (2 ^ {10} +1) \ mod41 [/ matemáticas]

[matemáticas] = (1023) (1025) \ mod41 [/ matemáticas]

[matemáticas] = (1023) (25) (41) \ mod41 [/ matemáticas]

[matemáticas] \ equiv0 \ mod41 \ text {} \ blacksquare [/ math]

[matemáticas] 2 ^ {20} -1 = 4 ^ {10} -1 = 16 ^ 5-1 = 16 (16 ^ 2) ^ 2-1 [/ matemáticas]

[matemáticas] 16 ^ 2 = 100 + 2 (60) +36 \ equiv 18 + 2 (19) -5 \ equiv 18-8 \ equiv 10 \ mod {41} [/ matemáticas], entonces

[matemáticas] 16 (16 ^ 2) ^ 2-1 \ equiv 16 (100) -1 \ equiv 16 (18) -1 \ equiv 160 + 128-1 \ equiv -4 + 5-1 \ equiv 0 \ mod { 41} [/ matemáticas]

Básicamente, esto nos pide que demostremos que [matemáticas] 2 ^ {20} = 1 \ pmod {41} [/ matemáticas]. Debido a que 41 es un primo extraño, sabemos por el pequeño teorema de Fermat que [matemática] x ^ {(41-1) / 2} = 1 \ pmod {41} [/ matemática] siempre que [matemática] x [/ matemática] sea un módulo cuadrado no cero 41. (De hecho, contando raíces, esto es además un “si y solo si”; ver más abajo). Como [matemáticas] (41 – 1) / 2 = 20 [/ matemáticas], esto se aplica precisamente a lo que queremos saber. Ahora solo tenemos que mostrar que 2 es un módulo cuadrado 41.

Aquí invocamos otra herramienta teórica de gran número, la reciprocidad cuadrática, que nos permite determinar rápidamente qué valores son cuadrados y qué valores. En particular, nos dice que 2 es un módulo cuadrado un primo impar solo en caso de que el primo impar esté al lado de un múltiplo de 8. 41 está de hecho al lado de un múltiplo de 8 (en este caso, 40), entonces 2 es de hecho módulo cuadrado 41, y así hemos terminado.

Aunque he invocado la reciprocidad cuadrática aquí, en realidad podemos alinear el argumento relevante para aquellos que no están familiarizados con la reciprocidad cuadrática, de esta manera: Considere todos los [math] 40 [/ math] valores distintos de cero módulo [math] 41 [/ math]. Por el pequeño teorema de Fermat, sabemos que son las raíces [matemáticas] 40 [/ matemáticas] de [matemáticas] x ^ {40} – 1 = (x ^ {20} + 1) (x ^ {20} – 1) [/matemáticas]. Como ninguno de los factores puede tener más de 20 raíces, encontramos que cada factor tiene 20 raíces; en particular, hay 20 soluciones para [matemáticas] x ^ {20} = -1 [/ matemáticas]. Elija cualquiera de estas soluciones [matemáticas] x [/ matemáticas] y deje que [matemáticas] y = x ^ {10} + x ^ {- 10} [/ matemáticas] mientras [matemáticas] z = x ^ 5 + x ^ {- 5 }[/matemáticas]. Observe que [matemáticas] y ^ 2 = x ^ {20} + x ^ {- 20} + 2 = -1 + -1 + 2 = 0 [/ matemáticas]; así [matemáticas] y = 0 [/ matemáticas]. Luego observe que [matemáticas] z ^ 2 = x ^ {10} + x ^ {- 10} + 2 = y + 2 = 0 + 2 = 2 [/ matemáticas]. Por lo tanto, [math] 2 [/ math] es un módulo cuadrado [math] 41 [/ math]. Y en cuanto a nuestro problema original, [matemáticas] 2 ^ {20} = (z ^ 2) ^ {20} = z ^ {40} = 1 [/ matemáticas]. (Todas las ecuaciones aquí están en la tierra del módulo 41, por supuesto)

Comencemos factorizándolo.

= (2 ^ 10 + 1) (2 ^ 10 – 1)

= (2 ^ 10 + 1) (2 ^ 5 – 1) (2 ^ 5 + 1)

= 1025 (31) (33)

Obviamente 41 no factoriza en 31 o 33. ¿Factoriza en 1025?

1025/41 = 25.

Por lo tanto 41 es un factor de 2 ^ 20 -1

2 ^ 20–1

= （2 ^ 10 + 1） * （2 ^ 5 + 1） * （2 ^ 5–1）

= 1025 * 33 * 31

= 25 * 41 * 33 * 31