Euler pseudoprime


In arithmetic, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and
.
The motivation for this definition is the fact that all prime numbers p satisfy the above equation which can be deduced from Fermat's little theorem. Fermat's theorem asserts that if p is prime, and coprime to a, then ap−1 ≡ 1. Suppose that p>2 is prime, then p can be expressed as 2q + 1 where q is an integer. Thus, a − 1 ≡ 1, which means that a2q − 1 ≡ 0. This can be factored as ≡ 0, which is equivalent to a/2 ≡ ±1.
The equation can be tested rather quickly, which can be used for probabilistic primality testing. These tests are twice as strong as tests based on Fermat's little theorem.
Every Euler pseudoprime is also a Fermat pseudoprime. It is not possible to produce a definite test of primality based on whether a number is an Euler pseudoprime because there exist absolute Euler pseudoprimes, numbers which are Euler pseudoprimes to every base relatively prime to themselves. The absolute Euler pseudoprimes are a subset of the absolute Fermat pseudoprimes, or Carmichael numbers, and the smallest absolute Euler pseudoprime is 1729 = 7×13×19.

Relation to Euler–Jacobi pseudoprimes

The slightly stronger condition that
where n is an odd composite, the greatest common divisor of a and n equals 1, and is the Jacobi symbol, is the more common definition of an Euler pseudoprime.
See, for example, page 115 of the book by Koblitz listed below, page 90 of the book by Riesel, or page 1003 of.
A discussion of numbers of this form can be found at Euler–Jacobi pseudoprime. There are no absolute Euler–Jacobi pseudoprimes.
A strong probable prime test is even stronger than the Euler-Jacobi test but takes the same computational effort. Because of this advantage over the Euler-Jacobi test, prime-testing software is often based on the strong test.

Implementation in Lua">Lua (programming language)">Lua

function EulerTest
a = 2
if k 1 then return false
elseif k 2 then return true
else
if) then
return true
else
return false
end
end
end'''

Examples

nEuler pseudoprimes to 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,...
3121, 703, 1541, 1729, 1891, 2465, 2821, 3281, 4961, 7381, 8401, 8911,...
4341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911,...
5217, 781, 1541, 1729, 5461, 5611, 6601, 7449, 7813,...
6185, 217, 301, 481, 1111, 1261, 1333, 1729, 2465, 2701, 3421, 3565, 3589, 3913, 5713, 6533, 8365,...
725, 325, 703, 817, 1825, 2101, 2353, 2465, 3277, 4525, 6697, 8321,...
89, 21, 65, 105, 133, 273, 341, 481, 511, 561, 585, 1001, 1105, 1281, 1417, 1541, 1661, 1729, 1905, 2047, 2465, 2501, 3201, 3277, 3641, 4033, 4097, 4641, 4681, 4921, 5461, 6305, 6533, 6601, 7161, 8321, 8481, 9265, 9709,...
991, 121, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911,...
109, 33, 91, 481, 657, 1233, 1729, 2821, 2981, 4187, 5461, 6533, 6541, 6601, 7777, 8149, 8401,...
11133, 305, 481, 645, 793, 1729, 2047, 2257, 2465, 4577, 4921, 5041, 5185, 8113,...
1265, 91, 133, 145, 247, 377, 385, 1649, 1729, 2041, 2233, 2465, 2821, 3553, 6305, 8911, 9073,...
1321, 85, 105, 561, 1099, 1785, 2465, 5149, 5185, 7107, 8841, 8911, 9577, 9637,...
1415, 65, 481, 781, 793, 841, 985, 1541, 2257, 2465, 2561, 2743, 3277, 5185, 5713, 6533, 6541, 7171, 7449, 7585, 8321, 9073,...
15341, 1477, 1541, 1687, 1729, 1921, 3277, 6541, 9073,...
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,...
179, 91, 145, 781, 1111, 1305, 1729, 2149, 2821, 4033, 4187, 5365, 5833, 6697, 7171,...
1825, 49, 65, 133, 325, 343, 425, 1105, 1225, 1369, 1387, 1729, 1921, 2149, 2465, 2977, 4577, 5725, 5833, 5941, 6305, 6517, 6601, 7345,...
199, 45, 49, 169, 343, 561, 889, 905, 1105, 1661, 1849, 2353, 2465, 2701, 3201, 4033, 4681, 5461, 5713, 6541, 6697, 7957, 8145, 8281, 8401, 9997,...
2021, 57, 133, 671, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2761, 3201, 5461, 5473, 5713, 5833, 6601, 6817, 7999,...
2165, 221, 703, 793, 1045, 1105, 2465, 3781, 5185, 5473, 6541, 7363, 8965, 9061,...
2221, 69, 91, 105, 161, 169, 345, 485, 1183, 1247, 1541, 1729, 2041, 2047, 2413, 2465, 2821, 3241, 3801, 5551, 7665, 9453,...
2333, 169, 265, 341, 385, 481, 553, 1065, 1271, 1729, 2321, 2465, 2701, 2821, 3097, 4033, 4081, 4345, 4371, 4681, 5149, 6533, 6541, 7189, 7957, 8321, 8651, 8745, 8911, 9805,...
2425, 175, 553, 805, 949, 1541, 1729, 1825, 1975, 2413, 2465, 2701, 3781, 4537, 6931, 7501, 9085, 9361,...
25217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5731, 6601, 7449, 7813, 8029, 8911, 9881,...
269, 25, 27, 45, 133, 217, 225, 475, 561, 589, 703, 925, 1065, 2465, 3325, 3385, 3565, 3825, 4741, 4921, 5041, 5425, 6697, 8029, 9073,...
2765, 121, 133, 259, 341, 365, 481, 703, 1001, 1541, 1649, 1729, 1891, 2465, 2821, 2981, 2993, 3281, 4033, 4745, 4921, 4961, 5461, 6305, 6533, 7381, 7585, 8321, 8401, 8911, 9809, 9841, 9881,...
289, 27, 145, 261, 361, 529, 785, 1305, 1431, 2041, 2413, 2465, 3201, 3277, 4553, 4699, 5149, 7065, 8321, 8401, 9841,...
2915, 21, 91, 105, 341, 469, 481, 793, 871, 1729, 1897, 2105, 2257, 2821, 4371, 4411, 5149, 5185, 5473, 5565, 6097, 7161, 8321, 8401, 8421, 8841,...
3049, 133, 217, 341, 403, 469, 589, 637, 871, 901, 931, 1273, 1537, 1729, 2059, 2077, 2821, 3097, 3277, 4081, 4097, 5729, 6031, 6061, 6097, 6409, 6817, 7657, 8023, 8029, 8401, 9881,...

Least Euler pseudoprime to base ''n''

nLeast EPSPnLeast EPSPnLeast EPSPnLeast EPSP
193354565339721
234134216665989
312135967339925
4341363568251009
5217379693510125
618538397069102133
7253913371910351
894039728510415
9914121739105451
10942451741510615
11133432175911079
1265449761510891
13214513377391099
14154697877110111
153414765793911155
1615484980911265
1794925819111321
18255021829114115
1995125832111557
2021525184851169
2165539852111749
2221545586651189
23335598713311915
24255633888712077
25217572589912115
2695857909112233
2765591591912385
28960341922112425
2915611593251259
3049629945712625
311563341951411279
3225649966512849