Euler pseudoprime

An odd natural number n is called Euler pseudo-prime if it is a composite number that behaves in relation to a relatively prime to their base a like a prime number: namely, if the congruence

Is satisfied.

In other words, n must divide the sum or the difference.

A consequence of the small Fermat's theorem

An Euler pseudoprime is pseudoprime with respect to a consequence of the Fermat's little theorem:

P is an odd prime, it shall, so also one of the two factors (third binomial formula ). For example, 7 is a divisor of 36-1 = 728 = 26.28 and one of the factors is divisible by 7. This criterion can be used for primality testing. As usual, called the composite numbers that satisfy the criterion, pseudo prime numbers ( with respect to the considered property).

Each Euler pseudoprime is a Fermat pseudoprime ( one squaring both sides of the congruence ). They are named after Leonhard Euler.

Definition

There are two variants to define the term Euler pseudoprime. Both cases assume that the base of a relatively prime to n.

Euler pseudoprime

An odd composite natural number is called Euler pseudoprime to the base a if

Applies.

Euler -Jacobi pseudoprime

An odd composite natural number is called Euler -Jacobi pseudoprime to the base a if

Applies. It denotes the Jacobi symbol. For prime n, this property is called euler cal criterion ( for the Legendre symbol ); it is intended for all primes p> 2:

Comparison

Apparently implies the second variant, the first (since for relatively prime a and n the Jacobi symbol, the values ​​ 1 and -1 assumes ). Examples n = 341, a = 2 or n = 21, a = 8 show that the inversion is incorrect. The second definition is therefore strictly stronger. The actions of the second definition is the basis of the Solovay - Strassen test.

A Fermat pseudoprime which is no Euler pseudoprime

The number n = 15 supplies to the base of a = 11 an example of a pseudo Fermat primes, which is not a prime pseudo Euler:

The following applies:

But

Note:

Absolute Euler pseudoprimes

Numbers representing a Euler pseudoprime to all bases coprime is called absolute Euler pseudo- prime numbers.