Un nombre composé impair est dit pseudo-premier d'Euler-Jacobi de base s'il est premier avec et si
où est le symbole de Jacobi.
Cette définition est motivée par le fait que tous les nombres premiers satisfont l'équation précédente, d'après le critère d'Euler. L'équation peut être testée assez rapidement, ce qui peut être utilisé pour les tests de primalité probabilistes. Ces tests sont plus de deux fois plus forts que les tests basés sur le petit théorème de Fermat.
Tout nombre pseudo-premier d'Euler-Jacobi est aussi un nombre pseudo-premier de Fermat et un nombre pseudo-premier d'Euler (vérifiant ). Il n'existe pas de nombre qui soit pseudo-premier d'Euler-Jacobi pour toutes les bases première avec lui : ce ne sont pas des nombres de Carmichael. Solovay et Strassen ont montré que pour tout nombre composé , pour au moins /2 bases inférieures à , n'est pas un nombre pseudo-premier d'Euler-Jacobi.
Ces nombres sont parfois appelés « nombres pseudo-premiers d'Euler ».
La table ci-dessous donne tous les nombres pseudo-premiers d'Euler-Jacobi inférieurs à pour les bases premières < 100.
a 2 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481 () 3 121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911 () 5 781, 1541, 1729, 5461, 5611, 6601, 7449, 7813 () 7 25, 325, 703, 2101, 2353, 2465, 3277, 4525 11 133, 793, 2047, 2465, 4577, 4921, 5041, 5185 13 85, 105, 1099, 1785, 5149, 7107, 8841, 8911, 9577, 9637 17 9, 91, 145, 781, 1111, 1305, 2821, 4033, 4187, 5365, 5833, 6697, 7171 19 9, 45, 49, 169, 343, 1849, 2353, 2701, 3201, 4033, 4681, 6541, 6697, 7957, 8281, 9997 23 169, 265, 553, 1271, 1729, 2465, 2701, 4033, 4371, 4681, 6533, 6541, 7189, 7957, 8321, 8651, 8911, 9805 29 15, 91, 341, 469, 871, 2257, 4371, 4411, 5149, 5185, 6097, 8401, 8841 31 15, 49, 133, 481, 931, 2465, 6241, 7449, 8911, 9131 37 9, 451, 469, 589, 685, 817, 1233, 1333, 1729, 3781, 3913, 4521, 5073, 8905, 9271 41 21, 105, 231, 671, 703, 841, 1065, 1281, 1387, 1417, 2465, 2701, 3829, 8321, 8911 43 21, 25, 185, 385, 925, 1541, 1729, 1807, 2465, 2553, 2849, 3281, 3439, 3781, 4417, 6545, 7081, 8857 47 65, 85, 221, 341, 345, 703, 721, 897, 1105, 1649, 1729, 1891, 2257, 2465, 5461, 5865, 6305, 9361, 9881 53 9, 27, 91, 117, 1405, 1441, 1541, 2209, 2529, 2863, 3367, 3481, 5317, 6031, 9409 59 15, 145, 451, 1141, 1247, 1541, 1661, 1991, 2413, 2465, 3097, 4681, 5611, 6191, 7421, 8149, 9637 61 15, 217, 341, 1261, 2465, 2701, 2821, 3565, 3661, 6541, 6601, 6697, 7613, 7905 67 33, 49, 217, 561, 703, 1105, 1309, 1519, 1729, 2209, 2245, 5797, 6119, 7633, 8029, 8371 71 9, 35, 45, 1387, 1729, 1921, 2071, 2209, 2321, 2701, 4033, 6541, 7957, 8365, 8695, 9809 73 9, 65, 205, 259, 333, 369, 533, 585, 1441, 1729, 1921, 2553, 2665, 3439, 5257, 6697 79 39, 49, 65, 91, 301, 559, 637, 1649, 2107, 2465, 2701, 3913, 6305, 6533, 7051, 8321, 9881 83 21, 65, 231, 265, 561, 689, 703, 861, 1105, 1241, 1729, 2665, 3277, 3445, 4411, 5713, 6601, 6973, 7665, 8421 89 9, 15, 45, 153, 169, 1035, 1441, 2097, 2611, 2977, 3961, 4187, 5461, 6697, 7107, 7601, 7711 97 49, 105, 341, 469, 481, 949, 973, 1065, 2701, 3283, 3577, 4187, 4371, 4705, 6811, 8023, 8119, 8911, 9313
Notes et références
Article connexe Nombre premier probable
Catégorie:Test de primalité Euler-Jacobi Catégorie:Leonhard Euler