Se n è un primo dispari, 
, per qualsiasi intero positivo b non multiplo di n, dove 
è il simbolo di Jacobi. Si dicono “pseudoprimi di Eulero – Jacobi”, ma anche talvolta semplicemente “pseudoprimi di Eulero”, rispetto alla base b i numeri composti dispari, che soddisfano la stessa congruenza.
Tutti gli pseudoprimi di Eulero – Jacobi sono anche pseudoprimi di Eulero (I) nella stessa base, ma non viceversa; per esempio, 341 e 5461 sono pseudoprimi di Eulero (I) in base 2, ma non pseudoprimi di Eulero – Jacobi; quindi verificare la congruenza costituisce un esame di primalità più forte che verificare se 
.
Tutti gli pseudoprimi forti di Fermat rispetto a una base sono anche pseudoprimi di Eulero – Jacobi, come dimostrò Selfridge; il viceversa vale sempre se lo pseudoprimo diviso per 4 dà resto 3 (Malm 1977) oppure se la base non è residuo quadratico di p (Pomerance, Selfridge e Wagstaff, 1980).
Nel 1986 Kiss, Phong e Lieuwens dimostrarono che per ogni base esistono infiniti pseudoprimi di Eulero – Jacobi, con ogni numero fissato di fattori primi.
Tutti i numeri di Mersenne composti Mp con p primo e tutti i numeri di Fermat composti sono pseudoprimi forti di Fermat in base 2 e quindi pseudoprimi di Eulero – Jacobi nella stessa base.
Nel 1976 D.H Lehmer dimostrò che per ogni numero composto vi è almeno una base rispetto alla quale non è pseudoprimo di Eulero – Jacobi e nel 1977 Robert M. Solovay e Volker Strassen dimostrarono che un numero composto n può essere pseudoprimo di Eulero – Jacobi rispetto al massimo a 
basi minori di n e prime rispetto a n, quindi non esiste tra gli pseudoprimi di Eulero – Jacobi un analogo dei numeri di Carmichael o degli pseudoprimi assoluti di Eulero, pseudoprimi in tutte le basi prime rispetto al numero.
Nel 1980 Monier dimostrò che il numero di basi rispetto alle quali un intero composto dispari n è pseudoprimo di Eulero – Jacobi è esattamente 
, dove δ(n) vale:
-
2, se e2(n) – 1 = e(n);
-
, se esiste un primo p che divide n, tale che ep(n) sia dispari e e2(p – 1) < e2(n – 1); -
1 altrimenti.
In queste formule ep(n) indica l’esponente della massima potenza di p che divide n e 
.
I numeri composti n che sono pseudoprimi di Eulero – Jacobi rispetto a 
basi, il massimo numero possibile, sono i numeri di Carmichael speciali, ossia i numeri interi n non multipli di quadrati, tali che p – 1 divida 
per ogni primo p che divide n (Lorenzo Di Biagio, 2011).
Il test di primalità di Solovay – Strassen si basa sul verificare se un numero è pseudoprimo di Eulero – Jacobi rispetto a varie basi: scegliendo k basi a caso, la probabilità che un numero composto superi l’esame è minore di 2–n e aumentando il numero delle basi, si riduce a piacere la probabilità di errore.
La tabella seguente mostra gli pseudoprimi di Eulero – Jacobi minori di 10000 nelle basi da 2 a 100.
|
Base |
Pseudoprimi di Eulero – Jacobi |
|
2 |
561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481 |
|
3 |
121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911 |
|
4 |
341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911 |
|
5 |
781, 1541, 1729, 5461, 5611, 6601, 7449, 7813 |
|
6 |
217, 481, 1111, 1261, 1729, 2701, 3589, 3913, 5713, 6533 |
|
7 |
25, 325, 703, 2101, 2353, 2465, 3277, 4525 |
|
8 |
9, 65, 105, 273, 481, 511, 561, 585, 1001, 1105, 1281, 1417, 1729, 1905, 2047, 2465, 2501, 3201, 3277, 3641, 4033, 4097, 4641, 4681, 4921, 6305, 6601, 7161, 8321, 8481, 9265 |
|
9 |
91, 121, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911 |
|
10 |
9, 91, 481, 1729, 4187, 6533, 6601, 8149, 8401 |
|
11 |
133, 793, 2047, 2465, 4577, 4921, 5041, 5185 |
|
12 |
91, 133, 145, 247, 385, 1649, 1729, 2041, 2233, 2821, 3553, 8911, 9073 |
|
13 |
85, 105, 1099, 1785, 5149, 7107, 8841, 8911, 9577, 9637 |
|
14 |
15, 65, 793, 841, 2465, 2743, 3277, 5713, 6541, 7171, 7449, 7585, 9073 |
|
15 |
1687, 1729, 1921, 3277, 6541 |
|
16 |
15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071, 2465, 2701, 2821, 3133, 3277, 3367, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5461, 5551, 6601, 6643, 7957, 8321, 8481, 8695, 8911, 9061, 9131, 9211, 9605, 9919 |
|
17 |
9, 91, 145, 781, 1111, 1305, 2821, 4033, 4187, 5365, 5833, 6697, 7171 |
|
18 |
25, 49, 65, 325, 343, 425, 1105, 1225, 1369, 1387, 1729, 1921, 2465, 2977, 4577, 5725, 5833, 5941, 6305, 6601, 7345 |
|
19 |
9, 45, 49, 169, 343, 1849, 2353, 2701, 3201, 4033, 4681, 6541, 6697, 7957, 8281, 9997 |
|
20 |
21, 671, 889, 1281, 1729, 1891, 2059, 2761, 3201, 5461, 6601, 7999 |
|
21 |
221, 703, 793, 1045, 3781, 7363, 9061 |
|
22 |
21, 91, 169, 345, 485, 1183, 1247, 2047, 2465, 5551, 7665 |
|
23 |
169, 265, 553, 1271, 1729, 2465, 2701, 4033, 4371, 4681, 6533, 6541, 7189, 7957, 8321, 8651, 8911, 9805 |
|
24 |
25, 175, 553, 949, 1541, 1729, 1825, 1975, 2701, 4537, 6931, 7501, 9361 |
|
25 |
217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5731, 6601, 7449, 7813, 8029, 8911, 9881 |
|
26 |
9, 25, 27, 45, 217, 225, 475, 703, 925, 1065, 3825, 5041, 5425, 8029, 9073 |
|
27 |
121, 133, 259, 365, 481, 703, 1649, 1729, 1891, 2821, 3281, 4033, 4921, 5461, 7381, 7585, 8401, 8911, 9809, 9841, 9881 |
|
28 |
9, 27, 261, 361, 529, 785, 1431, 2041, 2465, 3201, 3277, 4699, 5149, 7065, 8401 |
|
29 |
15, 91, 341, 469, 871, 2257, 4371, 4411, 5149, 5185, 6097, 8401, 8841 |
|
30 |
49, 133, 341, 403, 637, 871, 901, 931, 1729, 2059, 2077, 3277, 4081, 4097, 6031, 6409, 8023, 8401, 9881 |
|
31 |
15, 49, 133, 481, 931, 2465, 6241, 7449, 8911, 9131 |
|
32 |
25, 33, 205, 217, 325, 385, 465, 561, 793, 825, 1025, 1057, 1065, 1105, 1353, 1525, 1705, 1729, 1905, 2047, 2465, 2665, 2761, 3277, 4033, 4141, 4681, 5185, 5425, 6601, 6665, 6697, 7905, 8305, 8321, 8481, 8569, 9017, 9073 |
|
33 |
545, 1057, 1105, 1417, 1649, 2501, 5461, 5713, 5833, 6533, 6601, 9073, 9265 |
|
34 |
33, 35, 165, 273, 671, 1001, 1157, 2059, 2071, 2937, 4033, 6533, 6945, 7861, 8911 |
|
35 |
9, 153, 561, 1261, 2701, 2871, 5083, 5161 |
|
36 |
35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 4123, 4495, 5713, 6533, 6601, 8029, 8365, 8911, 9331, 9881 |
|
37 |
9, 451, 469, 589, 685, 817, 1233, 1333, 1729, 3781, 3913, 4521, 5073, 8905, 9271 |
|
38 |
39, 85, 91, 289, 469, 481, 871, 1445, 2553, 4033, 4681, 5461, 6031, 6097, 6931, 7449, 7585, 7613, 8177 |
|
39 |
133, 1561, 2047, 2465, 3053, 3439, 4141, 4237, 5921, 6533, 6601, 8149, 8911 |
|
40 |
39, 121, 289, 451, 533, 703, 1561, 1729, 1921, 4961, 5729, 6601, 7111, 7201, 9881 |
|
41 |
21, 105, 231, 671, 703, 841, 1065, 1281, 1387, 1417, 2465, 2701, 3829, 8321, 8911 |
|
42 |
451, 529, 1247, 1541, 1765, 1807, 1991, 6001, 7421, 9773 |
|
43 |
21, 25, 185, 385, 925, 1541, 1729, 1807, 2465, 2553, 2849, 3281, 3439, 3781, 4417, 6545, 7081, 8857 |
|
44 |
9, 15, 45, 301, 703, 1035, 1937, 1981, 2047, 2465, 4005, 4097, 4633, 6273, 8385 |
|
45 |
481, 1541, 1729, 1981, 2059, 2071, 3289, 4921, 6601, 8321, 9361 |
|
46 |
9, 15, 45, 341, 657, 721, 781, 949, 1729, 1891, 1991, 2071, 2117, 2201, 2465, 3201, 4033, 4089, 4187, 4465, 4681, 5611, 8321, 9211 |
|
47 |
65, 85, 221, 341, 345, 703, 721, 897, 1105, 1649, 1729, 1891, 2257, 2465, 5461, 5865, 6305, 9361, 9881 |
|
48 |
49, 259, 427, 481, 637, 703, 793, 1729, 1813, 1891, 1921, 2257, 2305, 2353, 2821, 2989, 4465, 5185, 5951, 6697, 6721, 8869, 8911, 9881 |
|
49 |
25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321 |
|
50 |
49, 51, 561, 697, 793, 817, 833, 1281, 1649, 1729, 2009, 2041, 2501, 2701, 3201, 3913, 4753, 6601, 8041, 8113, 9073, 9577 |
|
51 |
25, 65, 175, 325, 1247, 1681, 2059, 2653, 2821, 3053, 5461, 8365, 9475 |
|
52 |
51, 671, 901, 1891, 2653, 2705, 3201, 4081, 5151, 7201, 8911, 9773 |
|
53 |
9, 27, 91, 117, 1405, 1441, 1541, 2209, 2529, 2863, 3367, 3481, 5317, 6031, 9409 |
|
54 |
55, 265, 341, 361, 385, 1247, 1729, 2701, 2863, 4033, 4069, 4081, 7957, 9073 |
|
55 |
9, 27, 153, 801, 1027, 1387, 1513, 2821, 4033, 6533, 9773 |
|
56 |
55, 57, 247, 285, 1027, 1501, 1705, 1891, 2465, 3193, 3277, 3553, 5665, 6441 |
|
57 |
25, 65, 125, 325, 1001, 1625, 2047, 2465, 2911, 3193, 4187, 7501, 7613 |
|
58 |
57, 133, 671, 1141, 1441, 2065, 3009, 3097, 3365, 3781, 7471, 7991, 8119, 8749, 9073 |
|
59 |
15, 145, 451, 1141, 1247, 1541, 1661, 1991, 2413, 2465, 3097, 4681, 5611, 6191, 7421, 8149, 9637 |
|
60 |
481, 841, 1729, 1891, 3133, 3277, 3601, 3661, 4577, 4777, 6533, 8917 |
|
61 |
15, 217, 341, 1261, 2465, 2701, 2821, 3565, 3661, 6541, 6601, 6697, 7613, 7905 |
|
62 |
9, 21, 63, 91, 231, 361, 549, 679, 793, 1261, 1281, 1541, 2465, 2871, 3367, 3439, 3845, 4141, 4577, 5185, 5917, 6533, 6697, 6921, 8827 |
|
63 |
529, 703, 841, 1147, 1985, 2071, 2465, 2509, 3379, 3683, 4033, 5161, 5461, 6119, 6533, 6943, 7711, 9073 |
|
64 |
9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1001, 1105, 1281, 1365, 1387, 1417, 1541, 1649, 1661, 1729, 1785, 1905, 2047, 2169, 2465, 2501, 2701, 2821, 3145, 3171, 3201, 3277, 3605, 3641, 4005, 4033, 4097, 4369, 4371, 4641, 4681, 4921, 5461, 5565, 5963, 6305, 6533, 6601, 6951, 7107, 7161, 7957, 8321, 8481, 8911, 9265, 9709, 9773, 9881, 9945 |
|
65 |
33, 289, 703, 1111, 1387, 1891, 1921, 2701, 4291, 6533, 6697, 8321, 9537, 9809 |
|
66 |
65, 469, 1105, 1541, 2071, 2911, 4291, 6097, 6601, 6953, 7969, 9211 |
|
67 |
33, 49, 217, 561, 703, 1105, 1309, 1519, 1729, 2209, 2245, 5797, 6119, 7633, 8029, 8371 |
|
68 |
25, 49, 69, 125, 185, 217, 247, 361, 637, 871, 925, 1225, 1273, 1519, 1771, 2185, 2413, 2725, 2821, 4033, 4625, 4693, 4921, 5425, 5713, 7705, 8241, 9025 |
|
69 |
35, 85, 91, 133, 247, 361, 1105, 1387, 1729, 1921, 2527, 3605, 4693, 5713, 6161, 6643, 7345, 8911 |
|
70 |
69, 169, 341, 377, 561, 671, 949, 1891, 2769, 3053, 3201, 4901, 6001, 6177, 7449, 9301, 9361 |
|
71 |
9, 35, 45, 1387, 1729, 1921, 2071, 2209, 2321, 2701, 4033, 6541, 7957, 8365, 8695, 9809 |
|
72 |
85, 305, 451, 793, 1037, 1105, 1241, 1387, 1729, 2465, 4381, 5185, 5257, 6601, 6697, 8449 |
|
73 |
9, 65, 205, 259, 333, 369, 533, 585, 1441, 1729, 1921, 2553, 2665, 3439, 5257, 6697 |
|
74 |
15, 25, 75, 91, 325, 365, 427, 511, 793, 949, 1387, 1525, 1729, 1825, 4453, 4577, 5551, 6541, 6643, 7421 |
|
75 |
91, 133, 247, 289, 427, 481, 793, 1159, 1729, 1849, 1891, 2257, 2413, 2701, 2813, 2821, 4033, 4681, 4921, 5551, 7957, 8113, 8911, 9211 |
|
76 |
15, 25, 75, 77, 385, 949, 1113, 1369, 1417, 1825, 1891, 1925, 2289, 2701, 4033, 4681, 5777, 6533, 6545, 7957, 8365, 8745, 9211, 9673 |
|
77 |
39, 1387, 1513, 2465, 2701, 2965, 3705, 4371, 5073, 5461, 5713, 6541 |
|
78 |
77, 341, 451, 703, 1247, 1271, 1849, 1921, 2047, 2465, 3097, 4187, 4345, 6031, 6085, 6601 |
|
79 |
39, 49, 65, 91, 301, 559, 637, 1649, 2107, 2465, 2701, 3913, 6305, 6533, 7051, 8321, 9881 |
|
80 |
9, 27, 49, 81, 169, 301, 481, 1729, 2107, 3321, 3439, 5461, 6253, 6401, 6601, 7107, 7821, 8261, 8281, 8769 |
|
81 |
91, 121, 205, 511, 671, 697, 703, 949, 1105, 1387, 1541, 1729, 1891, 2465, 2501, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 6643, 7081, 7381, 7913, 8401, 8695, 8911 |
|
82 |
9, 25, 27, 81, 91, 225, 511, 891, 925, 949, 1345, 1525, 1541, 1825, 2025, 2257, 2465, 2871, 5611, 6533, 6643, 6725, 7957, 8321, 9919 |
|
83 |
21, 65, 231, 265, 561, 689, 703, 861, 1105, 1241, 1729, 2665, 3277, 3445, 4411, 5713, 6601, 6973, 7665, 8421 |
|
84 |
85, 1615, 2501, 2981, 3145, 5713, 6973, 7141, 8401 |
|
85 |
21, 341, 781, 1591, 2201, 3097, 3913, 4859, 7141, 7161, 7613, 8299 |
|
86 |
85, 87, 145, 493, 595, 1729, 2465, 3091, 5365, 7397, 7483, 9673 |
|
87 |
247, 403, 559, 589, 817, 1333, 1661, 1705, 3785, 5461, 6533, 7471, 7483, 7657, 8401, 9881 |
|
88 |
87, 247, 403, 589, 1891, 2047, 2465, 2581, 2611, 4331, 4849, 4921, 6697, 7657, 7745, 9073 |
|
89 |
9, 15, 45, 153, 169, 1035, 1441, 2097, 2611, 2977, 3961, 4187, 5461, 6697, 7107, 7601, 7711 |
|
90 |
91, 1001, 1157, 1729, 2413, 6281, 6601, 8321, 8401 |
|
91 |
9, 15, 45, 369, 1065, 1387, 2651, 3015, 4005, 4141, 4187, 5963, 6969, 9361, 9881 |
|
92 |
91, 93, 105, 301, 451, 559, 1001, 1209, 1393, 1729, 2465, 2587, 2701, 3731, 3781, 3913, 4033, 4371, 4641, 4681, 6697, 7161, 7905, 7957, 8321, 8465, 8557, 8841, 8911 |
|
93 |
25, 325, 793, 865, 1105, 1525, 1771, 2047, 2737, 3913, 4187, 4325, 4465, 4945, 5185, 5713, 5833, 6697, 6721, 8321, 8557, 8743, 8911 |
|
94 |
93, 95, 121, 133, 403, 465, 1105, 1729, 2465, 2977, 3053, 3565, 5685, 7099, 7471, 7905, 8743, 8911, 9073 |
|
95 |
1891, 2821, 2977, 3131, 3421, 4089, 6161, 8249, 9121 |
|
96 |
95, 485, 679, 1273, 1729, 2641, 2701, 4187, 5617, 6097, 9121, 9217, 9313 |
|
97 |
49, 105, 341, 469, 481, 949, 973, 1065, 2701, 3283, 3577, 4187, 4371, 4705, 6811, 8023, 8119, 8911, 9313 |
|
98 |
9, 33, 85, 99, 153, 561, 565, 873, 1017, 1105, 1649, 1705, 1921, 2465, 2701, 3007, 3201, 3277, 3585, 3729, 6817, 7345, 7471, 8321, 9605, 9703, 9881 |
|
99 |
25, 49, 169, 245, 361, 377, 775, 1225, 2413, 2465, 3277, 3565, 4225, 4901, 5611, 6889, 6943, 7825, 8281, 8321, 8695, 9425, 9703 |
|
100 |
9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 4141, 4187, 4521, 5461, 6533, 6541, 6601, 7107, 7471, 7777, 8149, 8401, 8911 |
La tabella seguente mostra il numero di pseudoprimi di Eulero – Jacobi in base 2 minori di 10n, per n fino a 19 (Jan Feitsma, William F. Galway, Carl Pomerance, John L. Selfridge, e Samuel S. Wagstaff, The Online Encyclopedia of Integer Sequences http://oeis.org).
|
n |
Pseudoprimi di Eulero – Jacobi |
|
10 |
0 |
|
102 |
0 |
|
103 |
1 |
|
104 |
12 |
|
105 |
36 |
|
106 |
114 |
|
107 |
375 |
|
108 |
1071 |
|
109 |
2939 |
|
1010 |
7706 |
|
1011 |
20417 |
|
1012 |
53332 |
|
1013 |
139597 |
|
1014 |
364217 |
|
1015 |
957111 |
|
1016 |
2526795 |
|
1017 |
6725234 |
|
1018 |
18069359 |
|
1019 |
48961462 |