Euler–Jacobi pseudoprime

In number theory, an odd integer n is called an Euler–Jacobi probable prime (or, more commonly, an Euler 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 (or, more commonly, an Euler 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 Legendre symbol 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 (see  A047713) (page 1005 of [1]).

In the literature (for example,[1]), 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.

n Euler–Jacobi pseudoprimes in base n
1 9, 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, ... (all odd composites)
2 561, 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, ...
3 121, 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, ...
4 341, 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, ...
5 781, 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, ...
6 217, 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, ...
7 25, 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, ...
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, 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, ...
9 91, 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, ...
10 9, 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, ...
11 133, 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, ...
12 91, 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, ...
13 85, 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, ...
14 15, 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, ...
15 1687, 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, ...
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, 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, ...
17 9, 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, ...
18 25, 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, ...
19 9, 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, ...
20 21, 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, ...
21 221, 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, ...
22 21, 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, ...
23 169, 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, ...
24 25, 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, ...
25 217, 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, ...
26 9, 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, ...
27 121, 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, ...
28 9, 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, ...
29 15, 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, ...
30 49, 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

n Smallest EJPSP n Smallest EJPSP n Smallest EJPSP n Smallest EJPSP
1 9 33 545 65 33 97 49
2 561 34 33 66 65 98 9
3 121 35 9 67 33 99 25
4 341 36 35 68 25 100 9
5 781 37 9 69 35 101 25
6 217 38 39 70 69 102 133
7 25 39 133 71 9 103 51
8 9 40 39 72 85 104 15
9 91 41 21 73 9 105 451
10 9 42 451 74 15 106 15
11 133 43 21 75 91 107 9
12 91 44 9 76 15 108 91
13 85 45 481 77 39 109 9
14 15 46 9 78 77 110 111
15 1687 47 65 79 39 111 55
16 15 48 49 80 9 112 65
17 9 49 25 81 91 113 57
18 25 50 49 82 9 114 115
19 9 51 25 83 21 115 57
20 21 52 51 84 85 116 9
21 221 53 9 85 21 117 49
22 21 54 55 86 85 118 9
23 169 55 9 87 247 119 15
24 25 56 55 88 87 120 91
25 217 57 25 89 9 121 15
26 9 58 57 90 91 122 65
27 121 59 15 91 9 123 85
28 9 60 481 92 91 124 25
29 15 61 15 93 25 125 9
30 49 62 9 94 93 126 25
31 15 63 529 95 1891 127 9
32 25 64 9 96 95 128 49

See also

References

  1. 1 2 Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·109" (PDF). Mathematics of Computation. 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7.
This article is issued from Wikipedia - version of the 12/2/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.