Catalan pseudoprime

Last updated

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.

Properties

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.

Related Research Articles

In number theory, a Carmichael number is a composite number which satisfies the modular arithmetic congruence relation:

In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.

In mathematics, a Fermat number, named after Pierre de Fermat, who first studied them, is a positive integer of the form

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.

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.

A Wilson prime, named after English mathematician John Wilson, is a prime number p such that p2 divides (p − 1)! + 1, where "!" denotes the factorial function; compare this with Wilson's theorem, which states that every prime p divides (p − 1)! + 1.

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 pseudoprime 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 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 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.

In number theory, the Fermat quotient of an integer a with respect to an odd prime p is defined as:

A pseudoprime is a probable prime that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.