Nombre pseudo-premier d'Euler-Jacobi
{{#invoke:Bandeau|ébauche}} Un nombre composé impair Modèle:Mvar est dit pseudo-premier d'Euler-Jacobi de base Modèle:Mvar s'il est premier avec Modèle:Mvar et si
où <math>\left(\frac an\right)</math> est le symbole de Jacobi.
Cette définition<ref>Modèle:Lien web</ref>,<ref>Modèle:Article</ref> est motivée par le fait que tous les nombres premiers Modèle:Mvar 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 <math>a^{(n-1)/2} \equiv \pm 1\pmod n</math>). 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<ref>Modèle:Article</ref> pour tout nombre composé Modèle:Mvar, pour au moins Modèle:Mvar/2 bases inférieures à Modèle:Mvar, Modèle:Mvar n'est pas un nombre pseudo-premier d'Euler-Jacobi.
Ces nombres sont parfois appelés « nombres pseudo-premiers d'Euler »<ref>Modèle:Article</ref>,<ref>Modèle:Lien web</ref>.
La table ci-dessous donne tous les nombres pseudo-premiers d'Euler-Jacobi inférieurs à 10 000 pour les bases premières Modèle:Mvar < 100.
| a | |
| 2 | 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481 (Modèle:OEIS) |
| 3 | 121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911 (Modèle:OEIS) |
| 5 | 781, 1541, 1729, 5461, 5611, 6601, 7449, 7813 (Modèle: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 |
Notes et références
Modèle:Traduction/Référence Modèle:Références
