Main Page | See live article | Alphabetical index

Euler-Jacobi pseudoprime

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 
2561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481 
3121, 1729, 2821, 7381, 8401 
5781, 1541, 1729, 5461, 5611, 6601, 7449 
725, 703, 2101, 2353, 2465, 3277 
11133, 793, 2465, 4577, 4921, 5041, 5185 
13105, 1785, 5149, 7107, 8841, 9577, 9637 
179, 145, 781, 1305, 2821, 4033, 5833, 6697 
199, 45, 49, 169, 1849, 2353, 3201, 4033, 4681, 6541, 6697, 8281 
23169, 265, 553, 1729, 2465, 4033, 4681, 6533, 6541, 7189, 8321, 8911 
2991, 341, 469, 871, 2257, 5149, 5185, 6097, 8401, 8841 
3115, 49, 133, 481, 2465, 6241, 7449, 9131 
379, 451, 469, 589, 817, 1233, 1333, 1729, 3781, 3913, 4521, 5073, 8905, 9271 
4121, 105, 841, 1065, 1281, 1417, 2465, 2701, 3829, 8321 
4321, 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, 
4765, 69, 341, 345, 481, 561, 703, 721, 793, 897, 1105, 1649, 1729, 1891, 2257, 2465, 2737, 3145,
     3201, 5185, 5461, 5865, 6305, 9361 
539, 65, 91, 117, 561, 585, 1105, 1441, 1541, 1729, 2209, 2465, 2529, 2821, 2863, 3097, 3367,
     3481, 3861, 5317, 5833, 6031, 6433, 9409 
59145, 451, 561, 645, 1105, 1141, 1247, 1541, 1661, 1729, 1991, 2413, 2465, 3097, 4681, 5611, 5729,
     6191, 6533, 6601, 7421, 8149, 8321, 8705, 9637 
6115, 93, 217, 341, 465, 1261, 1441, 1729, 2465, 2821, 3565, 3661, 4061, 4577,
     5461, 6541, 6601, 6697, 7613, 7905, 9305, 9937 
6733, 49, 217, 385, 561, 1105, 1309, 1519, 1705, 1729, 2209, 2465, 3201, 5797, 7633, 7701, 
8029, 8321, 8371, 9073 

See also: