EulerJacobi pseudoprime

From Example Problems
Jump to navigation Jump to search

In number theory, an odd composite integer n is called an Euler-Jacobi pseudoprime to base a, if a and n are coprime, and

a(n − 1)/2 = (a/n) (mod n),

where (a/n) is the Jacobi symbol.

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.

It should be noted that these numbers are, in some sources, called Euler pseudoprimes.

The table below gives all Euler-Jacobi pseudoprimes less than 10000 for some prime bases a, this table is in the process of being checked and should be used with caution until this notice is removed.

a  
2 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481
3 121, 1729, 2821, 7381, 8401
5 781, 1541, 1729, 5461, 5611, 6601, 7449
7 25, 703, 2101, 2353, 2465, 3277
11 133, 793, 2465, 4577, 4921, 5041, 5185
13 105, 1785, 5149, 7107, 8841, 9577, 9637
17 9, 145, 781, 1305, 2821, 4033, 5833, 6697
19 9, 45, 49, 169, 1849, 2353, 3201, 4033, 4681, 6541, 6697, 8281
23 169, 265, 553, 1729, 2465, 4033, 4681, 6533, 6541, 7189, 8321, 8911
29 91, 341, 469, 871, 2257, 5149, 5185, 6097, 8401, 8841
31 15, 49, 133, 481, 2465, 6241, 7449, 9131
37 9, 451, 469, 589, 817, 1233, 1333, 1729, 3781, 3913, 4521, 5073, 8905, 9271
41 21, 105, 841, 1065, 1281, 1417, 2465, 2701, 3829, 8321
43 21, 25, 33, 77, 105, 185, 385, 481, 561, 777, 825, 973, 1105, 1541, 1729, 1825, 2465, 2553, 2821, 2849, 3281, 3439, 3781, 4033, 4417, 6105, 6369, 6545, 6601, 6697, 7825
47 65, 69, 341, 345, 481, 561, 703, 721, 793, 897, 1105, 1649, 1729, 1891, 2257, 2465, 2737, 3145, 3201, 5185, 5461, 5865, 6305, 9361
53 9, 65, 91, 117, 561, 585, 1105, 1441, 1541, 1729, 2209, 2465, 2529, 2821, 2863, 3097, 3367, 3481, 3861, 5317, 5833, 6031, 6433, 9409
59 145, 451, 561, 645, 1105, 1141, 1247, 1541, 1661, 1729, 1991, 2413, 2465, 3097, 4681, 5611, 5729, 6191, 6533, 6601, 7421, 8149, 8321, 8705, 9637
61 15, 93, 217, 341, 465, 1261, 1441, 1729, 2465, 2821, 3565, 3661, 4061, 4577, 5461, 6541, 6601, 6697, 7613, 7905, 9305, 9937
67 33, 49, 217, 385, 561, 1105, 1309, 1519, 1705, 1729, 2209, 2465, 3201, 5797, 7633, 7701, 8029, 8321, 8371, 9073

See also

fr:Pseudopremier d'Euler-Jacobi