In arithmetic, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and
(where mod refers to the modulo operation).
The motivation for this definition is the fact that all prime numbers p satisfy the above equation which can be deduced from Fermat's little theorem. Fermat's theorem asserts that if p is prime, and coprime to a, then ap−1 ≡ 1 (mod p). Suppose that p>2 is prime, then p can be expressed as 2q + 1 where q is an integer. Thus, a(2q+1) − 1 ≡ 1 (mod p), which means that a2q − 1 ≡ 0 (mod p). This can be factored as (aq − 1)(aq + 1) ≡ 0 (mod p), which is equivalent to a(p−1)/2 ≡ ±1 (mod p).
The equation can be tested rather quickly, which can be used for probabilistic primality testing. These tests are twice as strong as tests based on Fermat's little theorem.
Every Euler pseudoprime is also a Fermat pseudoprime. It is not possible to produce a definite test of primality based on whether a number is an Euler pseudoprime because there exist absolute Euler pseudoprimes, numbers which are Euler pseudoprimes to every base relatively prime to themselves. The absolute Euler pseudoprimes are a subset of the absolute Fermat pseudoprimes, or Carmichael numbers, and the smallest absolute Euler pseudoprime is 1729 = 7×13×19.
In arithmetic, an odd composite integer n is called an Eulerpseudoprime to base a, if a and n are coprime, and a ( n − 1 ) / 2 ≡ ± 1 ( mod n ) {\displaystyle...
strong pseudoprime to base a is always an Euler–Jacobi pseudoprime, an Eulerpseudoprime and a Fermat pseudoprime to that base, but not all Euler and Fermat...
number is either an Euler–Jacobi pseudoprime or a strong pseudoprime to every base relatively prime to it so, in theory, either an Euler or a strong probable...
Euler's "lucky" numbers are positive integers n such that for all integers k with 1 ≤ k < n, the polynomial k2 − k + n produces a prime number. When k...
certainly composite. A composite number that passes such a test is called a pseudoprime. In contrast, some other algorithms guarantee that their answer will...
Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in...
If n is composite and satisfies the formula, then n is a Fibonacci pseudoprime. When m is large – say a 500-bit number – then we can calculate Fm (mod...
In mathematics, the Euler numbers are a sequence En of integers (sequence A122045 in the OEIS) defined by the Taylor series expansion 1 cosh t = 2 e...
In number theory, a Frobenius pseudoprime is a pseudoprime, whose definition was inspired by the quadratic Frobenius test described by Jon Grantham in...
conjectured that there are infinitely many lucky primes. Lucky numbers of Euler Fortunate number Happy number Harshad number Josephus problem Gambling Lottery...
In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem. Fermat's little theorem...
the case m = n − 1. Euler's rule creates additional amicable pairs for (m,n) = (1,8), (29,40) with no others being known. Euler (1747 & 1750) overall...
In number theory, a pseudoprime is called an elliptic pseudoprime for (E, P), where E is an elliptic curve defined over the field of rational numbers...
Two millennia later, Leonhard Euler proved that all even perfect numbers are of this form. This is known as the Euclid–Euler theorem. It is not known whether...
Design. doi:10.1201/9780429430701. ISBN 978-0-429-43070-1. S2CID 198342061. Euler, Leonhard; Lagrange, Joseph Louis (1810), Elements of Algebra, vol. 1 (2nd ed...
antiquity because of their close connection to perfect numbers: the Euclid–Euler theorem asserts a one-to-one correspondence between even perfect numbers...
Fermat number is a strong pseudoprime to base 2. This is because all strong pseudoprimes to base 2 are also Fermat pseudoprimes – i.e., 2 F n − 1 ≡ 1 (...
Solovay–Strassen test does not. This is because 1905 is an Eulerpseudoprime base 2 but not a strong pseudoprime base 2 (this is illustrated in Figure 1 of PSW)...
algorithm Fermat primality test Pseudoprime Carmichael number EulerpseudoprimeEuler–Jacobi pseudoprime Fibonacci pseudoprime Probable prime Baillie–PSW primality...
squares as a sum of squares Cubic number – Number raised to the third power Euler's four-square identity – Product of sums of four squares expressed as a sum...
4 case of Fermat's Last Theorem; see Fermat's right triangle theorem). Euler conjectured that a fourth power cannot be written as the sum of three fourth...
Global Information