Euler's pseudoprime number

An odd natural number n is called Euler's pseudoprime number if it is a composite number that behaves like a prime number in relation to a base a that is coprime to it: namely, if the congruence

${\displaystyle a^{\frac {n-1}{2}}\equiv \pm 1\mod n}$

is satisfied.

In other words, n must divide the difference or the sum . ${\displaystyle a^{\frac {n-1}{2}}-1}$ ${\displaystyle a^{\frac {n-1}{2}}+1}$

A consequence of Fermat's little theorem

An Euler pseudoprime is a pseudoprime related to a conclusion from Fermat's Little Theorem:

is p is an odd prime number, it shall , therefore, also one of the two factors ( third binomial formula ). For example, 7 is a factor of , and one of the factors is divisible by 7. This criterion can be used for primality tests. As usual, the composite numbers that meet the criterion are called pseudoprimes (in relation to the property under consideration). ${\displaystyle a^{p-1}-1}$ ${\displaystyle (a^{\frac {p-1}{2}}+1)(a^{\frac {p-1}{2}}-1)}$ ${\displaystyle 3^{6}-1=728=2^{3}\cdot 7\cdot 13}$

Every Euler pseudoprime is a Fermat pseudoprime (square both sides of the congruence). They are named after Leonhard Euler .

definition

There are two ways of defining the term Euler's pseudoprime . Both cases assume that the basis a is relatively prime to n .

Euler's pseudoprime number

An odd composite natural number is called Euler's pseudoprime with base a , if ${\displaystyle n}$

${\displaystyle a^{\frac {n-1}{2}}\equiv \pm 1\mod n}$

applies.

Euler-Jacobi pseudoprime

An odd composite natural number is called a Euler-Jacobi pseudoprime number with base a , if ${\displaystyle n}$

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

applies. The Jacobi symbol denotes . For prime n this property is called Euler's criterion (for the Legendre symbol ); namely for all prime numbers p > 2: ${\displaystyle \left({\frac {a}{n}}\right)}$

${\displaystyle a^{(p-1)/2}\equiv \left({\frac {a}{p}}\right)\mod p}$ .

comparison

Obviously, the second variant implies the first (since for coprime a and n the Jacobi symbol takes on the values ​​+1 and −1). The examples n = 341, a = 2 or n = 21, a = 8 show that the converse is wrong. So the second definition is really stronger. The procedure of the second definition is the basis of the Solovay-Strassen test .

A Fermat pseudoprime that is not an Euler pseudoprime

The number n = 15 with the base a = 11 provides an example of a Fermat pseudoprime that is not an Euler pseudoprime:

The following applies:

${\displaystyle 11^{14}\equiv 1\mod 15}$ ,

but

${\displaystyle 11^{7}\equiv 11\mod 15}$ ;

Note:

${\displaystyle 11^{2}=121\equiv 1\mod 15}$ .

Table with Euler pseudoprimes

The following is a table of the smallest Euler pseudo-prime numbers (at least less than or equal to 10000) based on base a :

a	Euler's pseudoprimes n with base a	OEIS episode
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, ... (any odd composite integer)
2	341, 561, 1105, 1729 , 1905, 2047, 2465 , 3277, 4033, 4681, 5461, 6601, 8321, 8481, 10261, ...	(Follow A006970 in OEIS )
3	121, 703, 1541, 1729 , 1891, 2465 , 2821, 3281, 4961, 7381, 8401, 8911, 10585, ...	(Follow A262051 in OEIS )
4th	341, 561, 645, 1105, 1387, 1729 , 1905, 2047, 2465 , 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, ...
5	217, 781, 1541, 1729 , 5461, 5611, 6601, 7449, 7813, 11041, ...	(Follow A262052 in OEIS )
6th	185, 217, 301, 481, 1111, 1261, 1333, 1729 , 2465 , 2701, 3421, 3565, 3589, 3913, 5713, 6533, 8365, 10585, ...	(Follow A262053 in OEIS )
7th	25, 325, 703, 817, 1825, 2101, 2353, 2465 , 3277, 4525, 6697, 8321, 10225, ...	(Follow A262054 in OEIS )
8th	9, 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, 10261, ...	(Follow A262055 in OEIS )
9	91, 121, 671, 703, 949, 1105, 1541, 1729 , 1891, 2465 , 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, ...
10	9, 33, 91, 481, 657, 1233, 1729 , 2821, 2981, 4187, 5461, 6533, 6541, 6601, 7777, 8149, 8401, ...
11	133, 305, 481, 645, 793, 1729 , 2047, 2257, 2465 , 4577, 4921, 5041, 5185, 8113, ...
...	...

The numbers 1729 and 2465 in bold are Euler pseudoprime numbers for all coprime bases a . In the line with base a = 5 , 2465 does not appear because and is therefore not coprime. Likewise, and therefore 1729 does not appear in the line with base a = 7 . Because of this , 2465 does not appear in the line with base a = 10 . These special Euler pseudoprimes are discussed in the next section. ${\displaystyle \operatorname {ggT} (5,2465)=5\not =1}$ ${\displaystyle \operatorname {ggT} (7,1729)=7\not =1}$ ${\displaystyle \operatorname {ggT} (10,2465)=5\not =1}$

Absolute Eulerian pseudoprimes

Numbers n , which represent an Euler pseudoprime for all coprime bases a , are called absolute Euler pseudoprimes . The first absolute Euler pseudoprimes are as follows:

1729, 2465, 15841, 41041, 46657, 75361, 162401, 172081, 399001, 449065, 488881, 530881, 656601, 670033, 838201, 997633, ... (sequence A033181 in OEIS )

Table with Euler-Jacobi pseudo-prime numbers

The following is a table of the smallest Euler-Jacobi pseudo-prime numbers (at least less than or equal to 10000) based on a . All these numbers appear in the previous table of Eulerian pseudoprimes, because the definition of the Euler-Jacobi pseudoprimes is stronger than the definition of the Eulerian pseudoprimes. Every Euler-Jacobi pseudoprime is also an Euler pseudoprime (the reverse does not apply):

a	Euler-Jacobi pseudoprimes n based on a	OEIS episode
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, ... (any odd composite integer)
2	561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481, 10585, ...	(Follow A047713 in OEIS )
3	121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911, 10585, ...	(Follow A48950 in OEIS )
4th	341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, 10261, ...
5	781, 1541, 1729, 5461, 5611, 6601, 7449, 7813, 11041, ...
6th	217, 481, 1111, 1261, 1729, 2701, 3589, 3913, 5713, 6533, 10585, ...
7th	25, 325, 703, 2101, 2353, 2465, 3277, 4525, 11041, ...
8th	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, ...
9	91, 121, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, 10585, ...
10	9, 91, 481, 1729, 4187, 6533, 6601, 8149, 8401, 10001, 11111, ...
11	133, 793, 2047, 2465, 4577, 4921, 5041, 5185, 12403, ...
...	...

In contrast to Euler's pseudoprimes, there are no numbers that are Euler-Jacobi pseudoprimes for all relatively prime bases a .

The number of Euler-Jacobi pseudoprimes with base a = 2 that are less than are the following: ${\displaystyle 10^{n}}$

0, 0, 1, 12, 36, 114, 375, 1071, 2939, 7706, 20417, 53332, 124882 (sequence A55551 in OEIS )

This means, for example, that there are 375 Euler-Jacobi pseudoprimes with base a = 2 that are less than , because 375 is the seventh number in the above sequence. ${\displaystyle 10^{7}}$

Summary

• Every Euler-Jacobi pseudo-prime number on the base a is also at the same time an Eulerian pseudo-prime number on the base a . The converse does not hold, that is, there are Euler pseudoprimes with base a that are not at the same time Euler-Jacobi pseudoprimes with base a .
• Every Euler pseudoprime with base a is also a Fermat pseudoprime with base a . The reverse is not true, that is, there are Fermat pseudoprimes with base a that are not at the same time Euler pseudoprimes with base a .
• Every Euler-Jacobi pseudoprime based on a is also a Fermat pseudoprime based on a . The reverse is not true, that is, there are Fermat pseudoprimes with base a that are not at the same time Euler-Jacobi pseudoprimes with base a .

Mathematically using set notation , the above is formulated as follows:

Euler-Jacobi pseudoprime Euler's pseudoprime Fermat's pseudoprime ${\displaystyle \subsetneqq }$ ${\displaystyle \subsetneqq }$

literature

• Neil Koblitz: A Course in Number Theory and Cryptography. 2nd edition. Springer, New York NY et al. 1994, ISBN 3-540-96576-9 ( Graduate Texts in Mathematics 114).
• Paul Erdős and Carl Pomerance : On the Number of False Witnesses for a Composite Number. Mathematics of Computation 46 , 259-279, 1986.
• Carl Pomerance: The Search for Prime Numbers. Scientific American 12/1982.
  German translation: Prime numbers in the rapid test. Spectrum of Science 02/1983. With a photo of a replica of Lehmer's bike chain computer from 1926.
• Carl Pomerance: Computational Number Theory. In: Timothy Gowers (Ed.): The Princeton companion to mathematics. Pp. 348–362, Princeton University Press, 2008 ( online ; PDF; 249 kB).
• Paulo Ribenboim : The New Book of Prime Number Records. Springer-Verlag, 1996.

See also

• Strong pseudoprime
• Super Euler's pseudoprime number

Web links

• Modulo calculator online

Individual evidence

1. ↑ Eric W. Weisstein: "Euler Pseudoprime." (MathWorld)
2. ↑ Eric W. Weisstein: "Euler-Jacobi Pseudoprime." (MathWorld)