在數論中，奇數整數n被稱為歐拉－雅可比偽素數（Euler–Jacobi可比偽素數）（或者更常見的是歐拉可能素數）。
基本介紹
- 中文名：歐拉－雅可比偽素數
- 外文名：Euler–Jacobi pseudoprime
介紹,屬性,例子,
介紹
如果a和n是互質的，那么
其中
是雅可比符號。
如果
是滿足上述同餘的奇數複合整數，那么被稱為Euler-Jacobi pseudoprime（或者更常見的是Euler pseudoprime）以基於
。
如果
屬性
這個定義的動機是所有素數n滿足上述等式的事實，如Legendre符號文章中所述。 可以相當快速地測試該等式，其可以用於機率素性測試。 這些測試的強度是基於費馬小定理的測試的兩倍。
每個歐拉－雅可比偽素數也是Fermat pseudoprime和Euler pseudoprime。 正如卡麥可數字那樣，沒有任何數字是Euler-Jacobi偽像到所有基數。 Solovay和Strassen表明，對於每個複合物n，對於小於n的至少n / 2個鹼基，n不是歐拉－雅可比偽素數.
最小的歐拉－雅可比偽素數2是561.有11347個歐拉－雅可比偽素數2小於25·109。
如上定義的歐拉－雅可比偽素數通常簡稱為Euler pseudoprime。
例子
下表給出了基數n≤30的所有Euler-Jacobi假性小於100000。
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, ... |
... | .... |
