Cómo demostrar que [matemáticas] 5 ^ {11 \ cdot 31} \ equiv 5 \ pmod {11 \ cdot 13} [/ matemáticas]

Answer 1

Los primos [math] p [/ math] satisfacen la congruencia [math] a ^ p \ equiv a \ pmod {p} [/ math], para cada entero [math] a [/ math]. Los seudoprimos a la base [matemática] a [/ matemática] son ​​números compuestos [matemática] n [/ matemática] que satisfacen [matemática] a ^ n \ equiv a \ pmod {n} [/ matemática]. El pseudoprimo más pequeño hasta la base 2 es [matemática] 341 = 11 \ cdot 31 [/ matemática]. De hecho, [math] 341 [/ math] es el pseudoprime más pequeño para cualquier base; no hay un pseudoprime más pequeño para basar [math] a [/ math], para cualquier [math] a [/ math].

---

Hay dos razones por las cuales el comentario anterior no se aplica: la base es [matemática] 5 [/ matemática], no [matemática] 2 [/ matemática], y el módulo es [matemática] 11 \ cdot 13 = 143 [/ matemática ] mientras que el poder es [matemáticas] 11 \ cdot 31 = 341 [/ matemáticas].

Aplicamos el teorema de Fermat, al igual que el Usuario de Quora antes que yo: Para primo [math] p [/ math], y [math] a [/ math] tal que [math] p \ nmid a [/ math], [math ] a ^ {p-1} \ equiv 1 \ pmod {p} [/ math]. Una versión equivalente es [math] a ^ p \ equiv a \ pmod {p} [/ math], para cada [math] a [/ math].

Tenemos [matemáticas] 5 ^ {341} = \ left (5 ^ {10} \ right) ^ {34} \ cdot 5 \ equiv 5 \ pmod {11} [/ math].

El módulo [matemáticas] 13 [/ matemáticas] es más difícil:

[matemáticas] 5 ^ {341} = \ left (5 ^ {12} \ right) ^ {28} \ cdot \ left (5 ^ 2 \ right) ^ 2 \ cdot 5 \ equiv 5 \ pmod {13}. [ /matemáticas]

Por lo tanto, [matemática] 5 ^ {341} -5 [/ matemática] es un múltiplo común de [matemática] 11 [/ matemática] y [matemática] 13 [/ matemática], por lo tanto, un múltiplo de [matemática] 143 [/ matemática] . [matemáticas] \ blacksquare [/ matemáticas]

Answer 2

Usa el pequeño teorema de Fermat varias veces …

Mod 11:
5 ^ (11 * 31) = (5 ^ 31) ^ 11 = 5 ^ 31 = (5 ^ 22) * (5 ^ 9) = ((5 ^ 2) ^ 11) * (5 ^ 9) = (5 ^ 2) * (5 ^ 9) = (5 ^ 11) = 5

Mod 13:
5 ^ (11 * 31) = 5 ^ (26 * 13 + 3) = ((5 ^ 26) ^ 13) * (5 ^ 3) = (5 ^ 26) * (5 ^ 3) = ((5 ^ 2) ^ 13) * (5 ^ 3) = (5 ^ 2) * (5 ^ 3) = (5 ^ 5) = 3125 = 13 * 240 + 5 = 5

Como 5 ^ (11 * 31) – 5 es divisible por 11 y 13, es divisible por su producto.