# Nombre pseudo-premier d'Euler-Jacobi

Un nombre composé impair n est dit pseudo-premier d'Euler-Jacobi de base a s'il est premier avec a et si
$a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}$
où $\left({\frac {a}{n}}\right)$ est le symbole de Jacobi.
Cette définition$^,$ est motivée par le fait que tous les nombres premiers n 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 $a^{(n-1)/2}\equiv \pm 1{\pmod {n}}$). 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é n, pour au moins n/2 bases inférieures à n, n 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 à 10 000 pour les bases premières a < 100.
| a | |
| 2 | 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481 (suite A047713 de l'OEIS) |
| 3 | 121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911 (suite A048950 de l'OEIS) |
| 5 | 781, 1541, 1729, 5461, 5611, 6601, 7449, 7813 (suite A262052 de l'OEIS) |
| 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 |