Nombre pseudo-premier d'Euler-Jacobi

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un nombre composé impair n est appelé pseudo-premier d'Euler-Jacobi de base a s'il est premier avec a et si

a^{(n-1)/2}\equiv\left(\frac an\right)\pmod n

\left(\frac an\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, comme expliqué dans l'article « Symbole de Legendre ». L'équation peut être testée plutôt rapidement, qui peut être utilisée 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.

Chaque pseudopremier d'Euler-Jacobi est aussi un pseudo-premier de Fermat et un 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 pour chaque composé n, pour au moins n/2 bases inférieures à n, n n'est pas un pseudopremier d'Euler-Jacobi.

Ces nombres sont, dans certaines sources, appelés « pseudo-premiers d'Euler ».

La table ci-dessous donne tous les pseudo-premiers d'Euler-Jacobi inférieurs à 10 000 pour certaines bases premières a.

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

Articles connexes[modifier | modifier le code]