In
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...
, an
odd
Odd means unpaired, occasional, strange or unusual, or a person who is viewed as eccentric.
Odd may also refer to:
Acronym
* ODD (Text Encoding Initiative) ("One Document Does it all"), an abstracted literate-programming format for describing X ...
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
''n'' is called an Euler–Jacobi probable prime (or, more commonly, an Euler probable prime) to base ''a'', if ''a'' and ''n'' are
coprime
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
, and
:
where
is the
Jacobi symbol
Jacobi symbol for various ''k'' (along top) and ''n'' (along left side). Only are shown, since due to rule (2) below any other ''k'' can be reduced modulo ''n''. Quadratic residues are highlighted in yellow — note that no entry with a ...
.
If ''n'' is an odd
composite
Composite or compositing may refer to:
Materials
* Composite material, a material that is made from several different substances
** Metal matrix composite, composed of metal and other parts
** Cermet, a composite of ceramic and metallic materials
...
integer that satisfies the above congruence, then ''n'' is called an Euler–Jacobi pseudoprime (or, more commonly, an Euler pseudoprime) to base ''a''.
Properties
The motivation for this definition is the fact that all
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s ''n'' satisfy the above equation, as explained in the
Euler's criterion article. The equation can be tested rather quickly, which can be used for probabilistic
primality testing
A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating wh ...
. These tests are over twice as strong as tests based on
Fermat's little theorem.
Every Euler–Jacobi pseudoprime is also a
Fermat pseudoprime
In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.
Definition
Fermat's little theorem states that if ''p'' is prime and ''a'' is coprime to ''p'', then ''a'p''− ...
and an
Euler pseudoprime In arithmetic, an odd composite integer ''n'' is called an Euler pseudoprime to base ''a'', if ''a'' and ''n'' are coprime, and
: a^ \equiv \pm 1\pmod
(where ''mod'' refers to the modulo operation).
The motivation for this definition is the f ...
. There are no numbers which are Euler–Jacobi pseudoprimes to all bases as
Carmichael number
In number theory, a Carmichael number is a composite number n, which in modular arithmetic satisfies the congruence relation:
:b^n\equiv b\pmod
for all integers b. The relation may also be expressed in the form:
:b^\equiv 1\pmod.
for all integers ...
s 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.
The smallest Euler–Jacobi pseudoprime base 2 is 561. There are 11347 Euler–Jacobi pseudoprimes base 2 that are less than 25·10
9 (see ) (page 1005 of
).
In the literature (for example,
), an Euler–Jacobi pseudoprime as defined above is often called simply an Euler pseudoprime.
See also
*
Probable prime
In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific con ...
References
{{DEFAULTSORT:Euler-Jacobi Pseudoprime
Pseudoprimes