Un número entero compuesto x se denomina pseudoprimo de Fermat respecto a la base de exponenciación entera a > 1, si x es divisor de . El pequeño teorema de Fermat establece que si p es primo y a es coprimo con respecto a p, entonces es divisible por p.

En otras palabras, un entero compuesto es un pseudoprimo de Fermat respecto a la base a si satisface el test de primalidad de Fermat para la base a. La declaración falsa de que todos los números que pasan la prueba de primalidad de Fermat para la base 2 son primos, se llama hipótesis china.

En teoría de números, los pseudoprimos de Fermat constituyen la clase más importante de números pseudoprimos que provienen de Pequeño teorema de Fermat.

Denominaciones Los pseudoprimos en base de exponenciación 2 a veces se denominan números de Sarrus, por P. F. Sarrus, que descubrió que 341 tiene esta propiedad; números de Poulet, por P. Poulet, que hizo una tabla de tales números, o fermatianos por Pierre de Fermat .

Un pseudoprimo de Fermat a menudo se denomina simplemente pseudoprimo, sobreentendiéndose el modificador de Fermat.

Un entero x que es un pseudoprimo de Fermat para todos los valores de a que son coprimos con x se denomina número de Carmichael.

Ejemplo El pseudoprimo 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: 2340 ≡ 1 (mod 341) y por lo tanto satisface el test de primalidad de Fermat para la base 2.

Propiedades

Distribución Hay infinitos pseudoprimos para cualquier base dada a > 1. En 1904, Cipolla demostró cómo producir un número infinito de pseudoprimos base a > 1: Sea p cualquier primo impar que no divide a (a2 - 1). Sea A = (ap - 1)/(a - 1) y sea B = (ap + 1)/(a + 1). Entonces n = AB es compuesto, y es un pseudoprimo respecto a la base a. Por ejemplo, si a = 2 y p = 5, entonces A = 31, B = 11 y n = 341 es un pseudoprimo respecto a la base 2.

De hecho, hay infinitos número pseudoprimo fuerte en cualquier base mayor que 1 (véase el teorema 1 del libro The pseudoprimes to 25·109 ) e infinitamente muchos números de Carmichael, pero son comparativamente raros. Hay tres pseudoprimos en base 2 por debajo de 1000, 245 por debajo de un millón y 21853 por debajo de 25·109. Hay 4842 pseudoprimos fuertes de base 2 y 2163 números de Carmichael por debajo de este límite (consúltese la mencionada tabla 1).

A partir de 17·257, el producto de números de Fermat consecutivos es un pseudoprimo de base 2, al igual que todos los compuestos de Fermat y los compuestos de Mersenne.

Factorizaciones Las factorizaciones de los 60 números de Poulet hasta 60787, incluidos los 13 números de Carmichael (en negrita), se encuentran en la siguiente tabla.

+ 34111 · 315613 · 11 · 176453 · 5 · 4311055 · 13 · 17138719 · 7317297 · 13 · 1919053 · 5 · 127204723 · 8924655 · 17 · 29270137 · 7328217 · 13 · 31327729 · 113403337 · 109436917 · 25743713 · 31 · 47+ 468131 · 151546143 · 12766017 · 23 · 41795773 · 109832153 · 15784813 · 11 · 25789117 · 19 · 671026131 · 331105855 · 29 · 73113055 · 7 · 17 · 19128013 · 17 · 251137417 · 13 · 1511374759 · 2331398111 · 31 · 411449143 · 337+ 1570923 · 683158417 · 31 · 73167055 · 13 · 257187053 · 5 · 29 · 431872197 · 1931995171 · 281230013 · 11 · 17 · 412337797 · 241257613 · 31 · 2772934113 · 37 · 61301217 · 13 · 3313088917 · 23 · 793141789 · 3533160973 · 43331621103 · 307+ 331533 · 43 · 257349455 · 29 · 2413533389 · 397398655 · 7 · 17 · 67410417 · 11 · 13 · 41416655 · 13 · 64142799127 · 3374665713 · 37 · 9749141157 · 31349981151 · 331526337 · 73 · 103552453 · 5 · 29 · 127574217 · 13 · 63160701101 · 6016078789 · 683

Un número de Poulet cuyos divisores d dividen a (2d − 2) se llama supernúmero de Poulet. Hay infinitos números de Poulet que no son supernúmeros de Poulet.

Pseudoprimos de Fermat más pequeños El pseudoprimo (p-p) más pequeño para cada base a ≤ 200 se da en la siguiente tabla; los colores marcan el número de factores primos. A diferencia de la definición al comienzo del artículo, los pseudoprimos por debajo de a están excluidos de la tabla (para los pseudoprimos por debajo de a, véase ).

La tabla siguiente está basada en la

a menor p-p a menor p-p a menor p-p a menor p-p14= 2²5165= 5 · 13101175= 5² · 7151175= 5² · 72341= 11 · 315285= 5 · 17102133= 7 · 19152153= 3² · 17391= 7 · 135365= 5 · 13103133= 7 · 19153209= 11 · 19415= 3 · 55455= 5 · 11104105= 3 · 5 · 7154155= 5 · 315124= 2² · 315563= 3² · 7105451= 11 · 41155231= 3 · 7 · 11635= 5 · 75657= 3 · 19106133= 7 · 19156217= 7 · 31725= 5²5765= 5 · 13107133= 7 · 19157186= 2 · 3 · 3189= 3²58133= 7 · 19108341= 11 · 31158159= 3 · 53928= 2² · 75987= 3 · 29109117= 3² · 13159247= 13 · 191033= 3 · 1160341= 11 · 31110111= 3 · 37160161= 7 · 231115= 3 · 56191= 7 · 13111190= 2 · 5 · 19161190= 2 · 5 · 191265= 5 · 136263= 3² · 7112121= 11²162481= 13 · 371321= 3 · 763341= 11 · 31113133= 7 · 19163186= 2 · 3 · 311415= 3 · 56465= 5 · 13114115= 5 · 23164165= 3 · 5 · 1115341= 11 · 3165112= 2⁴ · 7115133= 7 · 19165172= 2² · 431651= 3 · 176691= 7 · 13116117= 3² · 13166301= 7 · 431745= 3² · 56785= 5 · 17117145= 5 · 29167231= 3 · 7 · 111825= 5²6869= 3 · 23118119= 7 · 17168169= 13²1945= 3² · 56985= 5 · 17119177= 3 · 59169231= 3 · 7 · 112021= 3 · 770169= 13²120121= 11²170171= 3² · 192155= 5 · 1171105= 3 · 5 · 7121133= 7 · 19171215= 5 · 432269= 3 · 237285= 5 · 17122123= 3 · 41172247= 13 · 192333= 3 · 1173111= 3 · 37123217= 7 · 31173205= 5 · 412425= 5²7475= 3 · 5²124125= 5³174175= 5² · 72528= 2² · 77591= 7 · 13125133= 7 · 19175319= 11 · 192627= 3³7677= 7 · 11126247= 13 · 19176177= 3 · 592765= 5 · 1377247= 13 · 19127153= 3² · 17177196= 2² · 7²2845= 3² · 578341= 11 · 31128129= 3 · 43178247= 13 · 192935= 5 · 77991= 7 · 13129217= 7 · 31179185= 5 · 373049= 7²8081= 3⁴130217= 7 · 31180217= 7 · 313149= 7²8185= 5 · 17131143= 11 · 13181195= 3 · 5 · 133233= 3 · 118291= 7 · 13132133= 7 · 19182183= 3 · 613385= 5 · 1783105= 3 · 5 · 7133145= 5 · 29183221= 13 · 173435= 5 · 78485= 5 · 17134135= 3³ · 5184185= 5 · 373551= 3 · 1785129= 3 · 43135221= 13 · 17185217= 7 · 313691= 7 · 138687= 3 · 29136265= 5 · 53186187= 11 · 173745= 3² · 58791= 7 · 13137148= 2² · 37187217= 7 · 313839= 3 · 138891= 7 · 13138259= 7 · 37188189= 3³ · 73995= 5 · 198999= 3² · 11139161= 7 · 23189235= 5 · 474091= 7 · 139091= 7 · 13140141= 3 · 47190231= 3 · 7 · 1141105= 3 · 5 · 791115= 5 · 23141355= 5 · 71191217= 7 · 3142205= 5 · 419293= 3 · 31142143= 11 · 13192217= 7 · 314377= 7 · 1193301= 7 · 43143213= 3 · 71193276= 2² · 3 · 234445= 3² · 59495= 5 · 19144145= 5 · 29194195= 3 · 5 · 134576= 2² · 1995141= 3 · 47145153= 3² · 17195259= 7 · 3746133= 7 · 1996133= 7 · 19146147= 3 · 7²196205= 5 · 414765= 5 · 1397105= 3 · 5 · 7147169= 13²197231= 3 · 7 · 114849= 7²9899= 3² · 11148231= 3 · 7 · 11198247= 13 · 194966= 2 · 3 · 1199145= 5 · 29149175= 5² · 7199225= 3² · 5²5051= 3 · 17100153= 3² · 17150169= 13²200201= 3 · 67

Lista de pseudoprimos de Fermat en base fija n