En teoría de números , los pseudoprimos de Fermat constituyen la clase más importante de pseudoprimos que provienen del pequeño teorema de Fermat .
El pequeño teorema de Fermat establece que si p es primo y una es primos entre sí a p , entonces un p -1 - 1 es divisible por p . Para un entero a > 1, si un entero compuesto x divide a x −1 - 1, entonces x se denomina pseudoprime de Fermat a la base a . [1] : Def. 3.32 En otras palabras, un entero compuesto es un pseudoprime de Fermat a la base a si pasa con éxito la prueba de primalidad de Fermat.para la base a . [2] La afirmación falsa de que todos los números que pasan la prueba de primordialidad de Fermat para la base 2 son primos, se llama hipótesis china .
El pseudoprime de Fermat en base 2 más pequeño es 341. No es un primo, ya que es igual a 11 · 31, pero satisface el pequeño teorema de Fermat: 2 340 ≡ 1 (mod 341) y por lo tanto pasa la prueba de primalidad de Fermat para la base 2.
Los pseudoprimos de base 2 a veces se denominan números de Sarrus , en honor a PF Sarrus que descubrió que 341 tiene esta propiedad, números de Poulet , en honor a P. Poulet que hizo una tabla de tales números, o fermatianos (secuencia A001567 en la OEIS ).
Un entero x que es un pseudoprime de Fermat para todos los valores de a que son coprimos ax se llama número de Carmichael . [2] [1] : Def. 3.34
Hay infinitos pseudoprimos para cualquier base dada a > 1. En 1904, Cipolla mostró cómo producir un número infinito de pseudoprimos base a > 1: Sea p un primo que no divide a 2 - 1. Sea A = ( a p - 1) / ( a - 1) y sea B = ( a p + 1) / ( a + 1). Entonces n = AB es compuesto y es un pseudoprime a la base a . [3] Por ejemplo, si a = 2 y p = 5, entonces A = 31,B = 11 y n = 341 es un pseudoprime a la base 2.