Euler–Jacobi pseudoprime

From Wikipedia, the free encyclopedia
  (Redirected from Euler-Jacobi pseudoprime)
Jump to: navigation, search

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

a^{(n-1)/2} \equiv \left(\frac{a}{n}\right)\pmod{n}

where \left(\frac{a}{n}\right) is the Jacobi symbol.

If n is a composite integer that satisfies the above congruence, then n is called an Euler–Jacobi pseudoprime (or, more commonly, an Euler pseudoprime).

Properties[edit]

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 OEISA047713) (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[edit]

The table below gives all Euler–Jacobi pseudoprimes less than 10000 for some prime bases a.

a Euler–Jacobi pseudoprimes in base a
2 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481
3 121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911
5 781, 1541, 1729, 5461, 5611, 6601, 7449, 7813
7 25, 325, 703, 2101, 2353, 2465, 3277, 4525
11 133, 793, 2047, 2465, 4577, 4921, 5041, 5185
13 85, 105, 1099, 1785, 5149, 7107, 8841, 8911, 9577, 9637
17 9, 91, 145, 781, 1111, 1305, 2821, 4033, 4187, 5365, 5833, 6697, 7171
19 9, 45, 49, 169, 343, 1849, 2353, 2701, 3201, 4033, 4681, 6541, 6697, 7957, 8281, 9997
23 169, 265, 553, 1271, 1729, 2465, 2701, 4033, 4371, 4681, 6533, 6541, 7189, 7957, 8321, 8651, 8911, 9805
29 15, 91, 341, 469, 871, 2257, 4371, 4411, 5149, 5185, 6097, 8401, 8841
31 15, 49, 133, 481, 931, 2465, 6241, 7449, 8911, 9131
37 9, 451, 469, 589, 685, 817, 1233, 1333, 1729, 3781, 3913, 4521, 5073, 8905, 9271
41 21, 105, 231, 671, 703, 841, 1065, 1281, 1387, 1417, 2465, 2701, 3829, 8321, 8911
43 21, 25, 185, 385, 925, 1541, 1729, 1807, 2465, 2553, 2849, 3281, 3439, 3781, 4417, 6545, 7081, 8857
47 65, 85, 221, 341, 345, 703, 721, 897, 1105, 1649, 1729, 1891, 2257, 2465, 5461, 5865, 6305, 9361, 9881
53 9, 27, 91, 117, 1405, 1441, 1541, 2209, 2529, 2863, 3367, 3481, 5317, 6031, 9409
59 15, 145, 451, 1141, 1247, 1541, 1661, 1991, 2413, 2465, 3097, 4681, 5611, 6191, 7421, 8149, 9637
61 15, 217, 341, 1261, 2465, 2701, 2821, 3565, 3661, 6541, 6601, 6697, 7613, 7905
67 33, 49, 217, 561, 703, 1105, 1309, 1519, 1729, 2209, 2245, 5797, 6119, 7633, 8029, 8371
71 9, 35, 45, 1387, 1729, 1921, 2071, 2209, 2321, 2701, 4033, 6541, 7957, 8365, 8695, 9809
73 9, 65, 205, 259, 333, 369, 533, 585, 1441, 1729, 1921, 2553, 2665, 3439, 5257, 6697
79 39, 49, 65, 91, 301, 559, 637, 1649, 2107, 2465, 2701, 3913, 6305, 6533, 7051, 8321, 9881
83 21, 65, 231, 265, 561, 689, 703, 861, 1105, 1241, 1729, 2665, 3277, 3445, 4411, 5713, 6601, 6973, 7665, 8421
89 9, 15, 45, 153, 169, 1035, 1441, 2097, 2611, 2977, 3961, 4187, 5461, 6697, 7107, 7601, 7711
97 49, 105, 341, 469, 481, 949, 973, 1065, 2701, 3283, 3577, 4187, 4371, 4705, 6811, 8023, 8119, 8911, 9313

See also[edit]

References[edit]

  1. ^ a b Carl Pomerance; John L. Selfridge, Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·109". Mathematics of Computation 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7.