Ejercicio · ZW-TEST-DE-PRIMALIDAD-DE-FERMAT-010 · ★★★ Avanzado
Demuestra con el test de base 2 que 341 es compuesto, o explica por qué no puede detectarlo y qué base lo delata.
Elige una opción.
A La base 2 da \( 2^{340} \equiv 1 \pmod{341} \) y la prueba concluye que 341 es primo B La base 2 da \( 2^{340} \equiv 2 \pmod{341} \), así que 341 es primo C La base 2 da \( 2^{340} \equiv 0 \pmod{341} \), así que 341 es compuesto D La base 2 no lo detecta, pero la base 3 da \( 3^{340} \equiv 56 \pmod{341} \), lo que prueba que es compuesto Ver respuesta D. La base 2 no lo detecta, pero la base 3 da \( 3^{340} \equiv 56 \pmod{341} \), lo que prueba que es compuesto← Volver a la pregunta
Explicación Con base 2 la congruencia se cumple (341 = 11·31 es pseudoprimo base 2), pero con base 3 el residuo es 56 y no 1, lo que delata el compuesto.
El test de primalidad de Fermat es un criterio probabilístico para un entero \(n>1\): declara compuesto a \(n\) si, para alguna base \(a\) coprima con \(n\), la potencia \(a^{n-1}\) no es congruente con 1 módulo \(n\).
\[a^{n-1} \equiv 1 \pmod{n}\]
Más ejercicios de test de primalidad de fermat