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
où est le symbole de Jacobi.
Cette définition[réf. nécessaire] 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. Il n'existe pas de nombre qui est pseudo-premier d'Euler-Jacobi pour toutes les bases de la même manière que les nombres de Carmichael. Solovay et Strassen ont montré que[réf. souhaitée] 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 »[1].
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 |
| 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 |
