Euler–Jacobi pseudoprime


In number theory, an odd integer n is called an Euler–Jacobi probable prime to base a, if a and n are coprime, and
where is the Jacobi symbol.
If n is an odd composite integer that satisfies the above congruence, then n is called an Euler–Jacobi pseudoprime to base a.

Properties

The motivation for this definition is the fact that all prime numbers n satisfy the above equation, as explained in the Euler's criterion article. The equation can be tested rather quickly, which can be used for probabilistic primality testing. These tests are over twice as strong as tests based on Fermat's little theorem.
Every Euler–Jacobi pseudoprime is also a Fermat pseudoprime and an Euler pseudoprime. There are no numbers which are Euler–Jacobi pseudoprimes to all bases as Carmichael numbers are. Solovay and Strassen showed that for every composite n, for at least n/2 bases less than n, n is not an Euler–Jacobi pseudoprime.
The smallest Euler–Jacobi pseudoprime base 2 is 561. There are 11347 Euler–Jacobi pseudoprimes base 2 that are less than 25·109 .
In the literature, an Euler–Jacobi pseudoprime as defined above is often called simply an Euler pseudoprime.

Examples

The table below gives all Euler–Jacobi pseudoprimes less than 100000 for bases n ≤ 30.
nEuler–Jacobi pseudoprimes in base n
19, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 69, 75, 77, 81, 85, 87, 91, 93, 95, 99, 105, 111, 115, 117, 119, 121, 123, 125, 129, 133, 135, 141, 143, 145, 147, 153, 155, 159, 161, 165, 169, 171, 175, 177, 183, 185, 187, 189, 195, 201, 203, 205, 207, 209, 213, 215, 217, 219, 221, 225, 231, 235, 237, 243, 245, 247, 249, 253, 255, 259, 261, 265, 267, 273, 275, 279, 285, 287, 289, 291, 295, 297, 299,...
2561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481, 10585, 12801, 15841, 16705, 18705, 25761, 29341, 30121, 33153, 34945, 41041, 42799, 46657, 49141, 52633, 62745, 65281, 74665, 75361, 80581, 85489, 87249, 88357, 90751,...
3121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911, 10585, 12403, 15457, 15841, 16531, 18721, 19345, 23521, 24661, 28009, 29341, 31621, 41041, 44287, 46657, 47197, 49141, 50881, 52633, 55969, 63139, 63973, 74593, 75361, 79003, 82513, 87913, 88573, 93961, 97567,...
4341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, 10261, 10585, 11305, 12801, 13741, 13747, 13981, 14491, 15709, 15841, 16705, 18705, 18721, 19951, 23001, 23377, 25761, 29341, 30121, 30889, 31417, 31609, 31621, 33153, 34945, 35333, 39865, 41041, 41665, 42799, 46657, 49141, 49981, 52633, 55245, 57421, 60701, 60787, 62745, 63973, 65077, 65281, 68101, 72885, 74665, 75361, 80581, 83333, 83665, 85489, 87249, 88357, 88561, 90751, 91001, 93961,...
5781, 1541, 1729, 5461, 5611, 6601, 7449, 7813, 11041, 12801, 13021, 14981, 15751, 15841, 21361, 24211, 25351, 29539, 38081, 40501, 41041, 44801, 47641, 53971, 67921, 75361, 79381, 90241,...
6217, 481, 1111, 1261, 1729, 2701, 3589, 3913, 5713, 6533, 10585, 11041, 11137, 14701, 15841, 17329, 18361, 20017, 21049, 29341, 34441, 39493, 41041, 43621, 46657, 46873, 49141, 49321, 49661, 52633, 54481, 58969, 74023, 74563, 75361, 76921, 83333, 83665, 87061, 88561, 92053, 94657, 94697, 97751, 97921,...
725, 325, 703, 2101, 2353, 2465, 3277, 4525, 11041, 13665, 14089, 19345, 20197, 29857, 29891, 38081, 39331, 46657, 49241, 58825, 64681, 76627, 78937, 79381, 87673, 88399, 88831, 89961, 92929,...
89, 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, 10585, 10745, 11041, 12545, 12801, 13833, 14497, 15665, 15841, 16589, 16705, 16881, 17865, 18705, 19345, 19561, 20801, 23241, 24311, 24929, 25761, 29341, 30121, 32865, 33153, 33201, 34881, 34945, 35113, 37401, 38081, 40833, 41041, 41441, 42799, 43745, 45761, 46657, 49141, 49601, 50881, 52429, 52521, 52633, 52801, 54161, 55537, 55969, 56033, 57681, 59291, 59641, 61337, 62745, 64201, 65281, 65793, 66197, 69345, 69921, 73801, 74023, 74665, 75361, 77161, 80581, 85281, 85489, 87061, 87249, 88357, 90751, 92929, 94657, 95281, 96321, 97921,...
991, 121, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, 10585, 11011, 12403, 14383, 15203, 15457, 15841, 16471, 16531, 18721, 19345, 23521, 24661, 24727, 28009, 29161, 29341, 30857, 31621, 31697, 32791, 38503, 41041, 44287, 46657, 46999, 47197, 49051, 49141, 50881, 52633, 53131, 55261, 55969, 63139, 63973, 65485, 68887, 72041, 74593, 75361, 76627, 79003, 82513, 83333, 83665, 87913, 88561, 88573, 88831, 90751, 93961, 96139, 97567,...
109, 91, 481, 1729, 4187, 6533, 6601, 8149, 8401, 10001, 11111, 11169, 11649, 12801, 15841, 19201, 20961, 21931, 24013, 34441, 41041, 50851, 50881, 63973, 69921, 75361, 79003, 83119, 94139, 95161, 97681,...
11133, 793, 2047, 2465, 4577, 4921, 5041, 5185, 12403, 13333, 14521, 15841, 17711, 18705, 23377, 34945, 43213, 43739, 47611, 48283, 49105, 49141, 49601, 50737, 50997, 55537, 56057, 57929, 58969, 62745, 68137, 74089, 85879, 86347, 87913, 88831, 94945,...
1291, 133, 145, 247, 385, 1649, 1729, 2041, 2233, 2821, 3553, 8911, 9073, 10585, 12673, 13051, 13333, 13345, 13585, 14905, 15841, 16471, 18721, 19517, 20737, 20881, 21361, 24013, 24727, 25681, 26467, 26785, 27985, 29341, 29539, 30745, 31483, 31621, 33553, 34219, 34861, 35881, 37345, 38311, 38503, 38665, 40321, 41041, 46657, 49141, 52633, 53083, 59185, 61309, 63973, 65569, 66637, 67861, 74305, 75361, 78793, 79381, 79501, 80185, 87841, 88705, 88831, 89089, 93961, 97351,...
1385, 105, 1099, 1785, 5149, 7107, 8841, 8911, 9577, 9637, 13019, 14491, 15505, 17803, 19757, 20881, 22177, 23521, 26521, 30073, 30889, 35371, 44173, 45629, 49105, 54097, 56033, 57205, 70801, 75241, 82733, 83333, 85285, 86347, 87681, 91001,...
1415, 65, 793, 841, 2465, 2743, 3277, 5713, 6541, 7171, 7449, 7585, 9073, 12545, 15457, 18721, 21667, 22261, 23521, 34441, 38221, 38417, 40385, 40501, 41371, 46657, 49471, 58255, 68401, 71969, 79003, 88381, 90241, 91681, 95033, 96049, 97469,...
151687, 1729, 1921, 3277, 6541, 14041, 14701, 15409, 15841, 19201, 25313, 31021, 41041, 47461, 49241, 50401, 54241, 54649, 58969, 60691, 67249, 73801, 75361, 82733, 88831, 97921,...
1615, 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, 10261, 10585, 11305, 12403, 12801, 13019, 13741, 13747, 13981, 14351, 14491, 14701, 15051, 15211, 15709, 15841, 16021, 16471, 16705, 18705, 18721, 19669, 19951, 20191, 20485, 23001, 23377, 24727, 25351, 25761, 26335, 26599, 27511, 28645, 29341, 30121, 30889, 31417, 31609, 31621, 33153, 33227, 33355, 34945, 35333, 38503, 39865, 40501, 40951, 41041, 41665, 42121, 42127, 42799, 45551, 45991, 46513, 46657, 47197, 47611, 48599, 49141, 49155, 49981, 50737, 51319, 52633, 53131, 55245, 57421, 60701, 60787, 61447, 62745, 63973, 64821, 65077, 65281, 68101, 68251, 72631, 72885, 73555, 74563, 74665, 75361, 76627, 76921, 77879, 78013, 79003, 80581, 81631, 81915, 83333, 83665, 85489, 87249, 88357, 88561, 88831, 90751, 91001, 92701, 93961, 98671,...
179, 91, 145, 781, 1111, 1305, 2821, 4033, 4187, 5365, 5833, 6697, 7171, 12673, 15805, 19345, 19729, 21781, 22791, 24211, 26245, 31621, 33001, 33227, 34441, 35371, 38081, 42127, 46657, 49771, 62745, 71071, 74665, 77293, 78881, 80185, 88831, 93961, 96433, 97921, 98671,...
1825, 49, 65, 325, 343, 425, 1105, 1225, 1369, 1387, 1729, 1921, 2465, 2977, 4577, 5725, 5833, 5941, 6305, 6601, 7345, 10585, 11305, 11425, 12025, 15505, 15793, 15841, 18631, 19465, 22393, 22411, 27937, 28153, 29341, 30457, 30889, 35425, 39817, 39865, 40501, 41041, 41159, 43225, 46657, 49141, 50737, 52633, 54145, 60385, 60685, 60691, 74425, 75361, 80137, 84721, 89425, 90113, 90751, 91001, 94129, 99451, 99937,...
199, 45, 49, 169, 343, 1849, 2353, 2701, 3201, 4033, 4681, 6541, 6697, 7957, 8281, 9997, 12403, 13213, 13747, 13833, 15251, 16531, 18769, 19201, 19729, 24761, 30589, 31621, 31861, 32477, 34945, 37681, 41003, 41041, 47593, 49141, 49771, 59585, 63139, 64681, 65161, 66421, 68257, 73555, 75361, 96049,...
2021, 671, 889, 1281, 1729, 1891, 2059, 2761, 3201, 5461, 6601, 7999, 12801, 13051, 15311, 15841, 16441, 21667, 25681, 31369, 34861, 35169, 37901, 38989, 41041, 42127, 49771, 50737, 52521, 54811, 57981, 64681, 68251, 75361, 78961, 85591, 86241, 88831, 89281, 92509, 93031, 96049, 97921,...
21221, 703, 793, 1045, 3781, 7363, 9061, 10945, 11647, 13051, 17767, 19345, 19669, 19909, 22681, 27133, 30073, 30745, 31021, 35785, 38503, 38665, 41353, 43213, 46657, 58829, 79081, 80137, 83569, 85285, 88357, 92509, 96049,...
2221, 91, 169, 345, 485, 1183, 1247, 2047, 2465, 5551, 7665, 10465, 11557, 14111, 15229, 15841, 16393, 17169, 17767, 18705, 19909, 20881, 21667, 23651, 31417, 33465, 34945, 38503, 47197, 49141, 53131, 62745, 64907, 70579, 72581, 76921, 88705, 89281, 90851, 98385, 99541,...
23169, 265, 553, 1271, 1729, 2465, 2701, 4033, 4371, 4681, 6533, 6541, 7189, 7957, 8321, 8651, 8911, 9805, 11713, 14905, 14981, 18721, 19513, 19517, 20801, 25201, 28897, 31861, 34133, 38665, 41041, 44173, 44785, 46657, 47611, 47783, 50737, 52633, 57401, 62849, 75361, 80401, 82513, 86101, 93457, 96049,...
2425, 175, 553, 949, 1541, 1729, 1825, 1975, 2701, 4537, 6931, 7501, 9361, 10465, 10585, 12025, 13825, 14425, 15025, 15841, 19345, 19513, 21349, 25201, 25273, 25477, 29185, 29341, 29665, 35425, 38323, 40369, 41041, 42121, 42127, 43873, 46657, 47617, 49141, 50881, 52417, 52633, 55969, 63701, 75361, 80137, 83333, 83665, 85609, 88561, 89281, 94753,...
25217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5731, 6601, 7449, 7813, 8029, 8911, 9881, 11041, 12801, 13021, 13333, 13981, 14981, 15751, 15841, 16297, 17767, 21361, 22791, 23653, 24211, 25327, 25351, 29341, 29539, 30673, 32021, 35371, 36661, 36991, 38081, 40501, 41041, 42127, 44173, 44801, 45141, 46657, 47641, 48133, 50737, 50997, 52633, 53083, 53971, 56033, 58807, 63973, 67921, 68101, 68251, 75361, 79381, 88831, 90241, 98173,...
269, 25, 27, 45, 217, 225, 475, 703, 925, 1065, 3825, 5041, 5425, 8029, 9073, 11005, 11041, 13833, 16725, 17575, 23653, 24073, 24727, 25299, 25425, 31651, 33227, 35881, 47197, 55537, 60701, 61975, 63025, 68251, 70561, 76627, 79003, 85321, 91525, 93961, 95051, 96641,...
27121, 133, 259, 365, 481, 703, 1649, 1729, 1891, 2821, 3281, 4033, 4921, 5461, 7381, 7585, 8401, 8911, 9809, 9841, 9881, 10585, 11041, 12403, 13019, 13073, 13333, 15457, 15841, 16021, 16531, 18721, 19345, 21901, 23521, 24661, 26467, 26599, 27265, 28009, 29341, 29891, 31609, 31621, 35113, 35371, 37969, 41041, 44287, 46657, 47197, 48133, 49141, 50171, 50881, 52633, 52801, 55537, 55969, 58201, 59641, 63139, 63973, 69469, 74023, 74593, 75361, 79003, 79381, 82513, 82853, 87061, 87913, 88573, 92509, 92833, 92929, 93961, 94657, 97567, 97921, 98881,...
289, 27, 261, 361, 529, 785, 1431, 2041, 2465, 3201, 3277, 4699, 5149, 7065, 8401, 13357, 13833, 14981, 17767, 27133, 28009, 31753, 32551, 33227, 35443, 36801, 38503, 43213, 46657, 50737, 58969, 68143, 80137, 81317, 82513, 88705, 96139, 97567, 97831,...
2915, 91, 341, 469, 871, 2257, 4371, 4411, 5149, 5185, 6097, 8401, 8841, 11581, 12431, 15577, 15841, 16471, 19093, 22281, 25681, 27613, 28009, 29539, 31417, 33001, 41041, 46657, 48133, 49141, 54913, 57889, 79003, 98301,...
3049, 133, 341, 403, 637, 871, 901, 931, 1729, 2059, 2077, 3277, 4081, 4097, 6031, 6409, 8023, 8401, 9881, 11041, 11809, 15841, 17593, 24929, 26599, 27001, 27133, 30889, 33227, 38503, 41041, 42127, 43213, 48133, 50881, 52801, 54961, 56033, 57137, 63973, 65569, 66197, 75361, 79003, 92929, 96049,...

Least Euler-Jacobi pseudoprime to base ''n''

nSmallest EJPSPnSmallest EJPSPnSmallest EJPSPnSmallest EJPSP
193354565339749
256134336665989
312135967339925
4341363568251009
5781379693510125
621738397069102133
7253913371910351
894039728510415
9914121739105451
10942451741510615
11133432175911079
1291449761510891
13854548177391099
14154697877110111
1516874765793911155
1615484980911265
1794925819111357
18255049829114115
1995125832111557
2021525184851169
21221539852111749
2221545586851189
231695598724711915
24255655888712091
25217572589912115
2695857909112265
27121591591912385
28960481929112425
2915611593251259
3049629949312625
3115635299518911279
3225649969512849