查看“︁欧拉-雅可比伪素数”︁的源代码

{{TA|G1=Math}}
'''欧拉－雅可比伪素数'''（{{lang-en|Euler–Jacobi pseudoprime}}）是[[伪素数]]的一种。对于奇[[合数]]''n''以及与其[[互素]]的自然数''a''，如果
: <math>a^{(n-1)/2} \equiv \left(\frac{a}{n}\right)\pmod{n}</math>
成立（其中<math>\left(\frac{a}{n}\right)</math>为[[雅可比符号]]），则称''n''为以''a''為底的欧拉－雅可比伪素数，或简称为欧拉伪素数。

欧拉－雅可比伪素数是[[欧拉伪素数]]的推广，所有欧拉－雅可比伪素数同时也是[[费马伪素数]]与欧拉伪素数。由于上式对所有[[素数]]都成立，因而可以用其进行概率[[素性检验]]，其可靠性是[[费马素性检验]]的两倍多。此外，与绝对费马伪素数（[[卡迈克尔数]]）与绝对欧拉伪素数不同的是，不存在绝对欧拉－雅可比伪素数，即不存在以所有与''n''互素的''a''為底都是欧拉－雅可比伪素数的''n''。可以证明，对于''n''，至少存在''n/2''个小于''n''的''a''，''n''不是欧拉－雅可比伪素数。

以2為底的最小欧拉－雅可比伪素数是561。而在小于25·10<sup>9</sup>的数中，共有11347个以2為底的欧拉－雅可比伪素数（参见{{oeis|id=A047713}})）。<ref name="PSW">{{cite journal|author2=[[John L. Selfridge]]|author3=[[Samuel S. Wagstaff, Jr.]]|title=The pseudoprimes to 25·10<sup>9</sup>|journal=Mathematics of Computation|date=July 1980|volume=35|issue=151|pages=1003–1026|url=http://www.math.dartmouth.edu/~carlp/PDF/paper25.pdf|author1=[[Carl Pomerance]]|doi=10.1090/S0025-5718-1980-0572872-7|access-date=2016-09-22|archive-date=2016-12-03|archive-url=https://web.archive.org/web/20161203123325/https://math.dartmouth.edu/~carlp/PDF/paper25.pdf|dead-url=no}}</ref>

== 示例 ==
{|class="wikitable"
|-
|''n''
|以''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, ... 
|-
|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, ...
|}

== 关于''n''的最小欧拉－雅可比伪素数 ==
{|class="wikitable"
|''n''
|最小欧拉－雅可比伪素数
|''n''
|最小欧拉－雅可比伪素数
|''n''
|最小欧拉－雅可比伪素数
|''n''
|最小欧拉－雅可比伪素数
|-
|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
|-
|}

== 参见 ==
* [[费马伪素数]]
* [[卡迈克尔数]]
* [[欧拉伪素数]]
* [[強偽質數]]

== 参考文献 ==
{{reflist}}

{{質數}}
[[Category:伪素数]]