Euler pseudoprime
Encyclopedia
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 number
s 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.
The stronger condition that a(n−1)/2 = (a/n) (mod n), where (a,n) = 1 and (a/n) is the Jacobi symbol
, is sometimes used for a definition of an Euler pseudoprime. A discussion of numbers of this form can be found at Euler–Jacobi pseudoprime.
Arithmetic
Arithmetic or arithmetics is the oldest and most elementary branch of mathematics, used by almost everyone, for tasks ranging from simple day-to-day counting to advanced science and business calculations. It involves the study of quantity, especially as the result of combining numbers...
, an odd composite
Composite number
A composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
n is called an Euler pseudoprime to base a, if a and n are coprime
Coprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
, and
(where mod refers to the modulo
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
operation).
The motivation for this definition is the fact that all prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s p satisfy the above equation which can be deduced from Fermat's little theorem
Fermat's little theorem
Fermat's little theorem states that if p is a prime number, then for any integer a, a p − a will be evenly divisible by p...
. 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
Pseudoprime
In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.- Definition :...
. It is not possible to produce a definite test of primality based on whether a number
Number
A number is a mathematical object used to count and measure. In mathematics, the definition of number has been extended over the years to include such numbers as zero, negative numbers, rational numbers, irrational numbers, and complex numbers....
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
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of the absolute Fermat pseudoprimes, or Carmichael numbers, and the smallest absolute Euler pseudoprime is 1729
1729 (number)
1729 is the natural number following 1728 and preceding 1730.1729 is known as the Hardy–Ramanujan number after a famous anecdote of the British mathematician G. H. Hardy regarding a hospital visit to the Indian mathematician Srinivasa Ramanujan...
= 7×13×19.
The stronger condition that a(n−1)/2 = (a/n) (mod n), where (a,n) = 1 and (a/n) is the Jacobi symbol
Jacobi symbol
The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in...
, is sometimes used for a definition of an Euler pseudoprime. A discussion of numbers of this form can be found at Euler–Jacobi pseudoprime.