 | This article needs additional citations for verification .(December 2015) |
In mathematics, a Catalan pseudoprime is an odd composite number n satisfying the congruence
where Cm denotes the m-th Catalan number. The congruence also holds for every odd prime number n that justifies the name pseudoprimes for composite numbers n satisfying it.
The only known Catalan pseudoprimes are: 5907, 1194649, and 12327121 (sequence A163209 in the OEIS ) with the latter two being squares of Wieferich primes. In general, if p is a Wieferich prime, then p2 is a Catalan pseudoprime.
In number theory, a Carmichael number is a composite number which in modular arithmetic satisfies the congruence relation:
In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.
In number theory, Fermat's little theorem states that if p is a prime number, then for any integer a, the number ap − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as
In mathematics, a Fermat number, named after Pierre de Fermat (1607–1665), the first known to have studied them, is a positive integer of the form: where n is a non-negative integer. The first few Fermat numbers are: 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, ....
In number theory, an odd integer n is called an Euler–Jacobi probable prime to base a, if a and n are coprime, and
The Fermat primality test is a probabilistic test to determine whether a number is a 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 conditions. While there may be probable primes that are composite, the condition is generally chosen in order to make such exceptions rare.
The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen primality test.
In arithmetic, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and
In number theory, a Wieferich prime is a prime number p such that p2 divides 2p − 1 − 1, therefore connecting these primes with Fermat's little theorem, which states that every odd prime p divides 2p − 1 − 1. Wieferich primes were first described by Arthur Wieferich in 1909 in works pertaining to Fermat's Last Theorem, at which time both of Fermat's theorems were already well known to mathematicians.
In number theory, a Wall–Sun–Sun prime or Fibonacci–Wieferich prime is a certain kind of prime number which is conjectured to exist, although none are known.
The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen in 1977, is a probabilistic test to determine if a number is composite or probably prime. The idea behind the test was discovered by M. M. Artjuhov in 1967 (see Theorem E in the paper). This test has been largely superseded by the Baillie–PSW primality test and the Miller–Rabin primality test, but has great historical importance in showing the practical feasibility of the RSA cryptosystem. The Solovay–Strassen test is essentially an Euler–Jacobi probable prime test.
Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence.
In mathematics, Wolstenholme's theorem states that for a prime number , the congruence
In mathematics, in particular number theory, an odd composite number N is a Somer–Lucas d-pseudoprime (with given d ≥ 1) if there exists a nondegenerate Lucas sequence with the discriminant such that and the rank appearance of N in the sequence U(P, Q) is
In number theory, a Frobenius pseudoprime is a pseudoprime, whose definition was inspired by the quadratic Frobenius test described by Jon Grantham in a 1998 preprint and published in 2000. Frobenius pseudoprimes can be defined with respect to polynomials of degree at least 2, but they have been most extensively studied in the case of quadratic polynomials.
In number theory, a branch of mathematics, a Mirimanoff's congruence is one of a collection of expressions in modular arithmetic which, if they hold, entail the truth of Fermat's Last Theorem. Since the theorem has now been proven, these are now of mainly historical significance, though the Mirimanoff polynomials are interesting in their own right. The theorem is due to Dmitry Mirimanoff.
The Baillie–PSW primality test is a probabilistic or possibly deterministic primality testing algorithm that determines whether a number is composite or is a probable prime. It is named after Robert Baillie, Carl Pomerance, John Selfridge, and Samuel Wagstaff.
A pseudoprime is a probable prime that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy.
Classes of natural numbers | |||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
