Pseudoprime

A pseudoprime is a composite integer that satisfies a condition normally used to identify primes. The condition may depend on a chosen base or primality test.

Congruence relation: An equivalence relation on integers stating that two numbers have the same remainder upon division by a modulus. Fermat-style pseudoprimality is defined by a congruence modulo the composite integer.
Fermat pseudoprime: A composite n is a Fermat pseudoprime to base a when gcd(a,n)=1 and a^(n−1) is congruent to 1 modulo n. This is the standard base-dependent form of pseudoprimality.
341: The composite integer 341, equal to 11 times 31, is the smallest Fermat pseudoprime to base 2. It demonstrates that the base-2 Fermat test can accept a composite.
Strong pseudoprime: A composite n is a strong pseudoprime to an odd base a when it passes the corresponding Miller–Rabin test. It satisfies a stricter base-dependent condition than a Fermat pseudoprime.
Modular arithmetic: Arithmetic in which numbers are identified by their remainders modulo a fixed positive integer. Pseudoprime tests compare powers and residues within this arithmetic.
Fermat primality test: A probabilistic primality test that checks whether a^(n−1) is congruent to 1 modulo n for selected bases a. A composite passes the test when it is a Fermat pseudoprime to the tested base.
561: The composite integer 561, equal to 3 times 11 times 17, is the smallest Carmichael number. It passes Fermat's congruence for every base coprime to it.
Miller–Rabin primality test: A probabilistic primality test based on decomposing n−1 into a power of 2 times an odd integer and checking modular powers. Its strong-witness condition rejects many composites that pass Fermat's test.
Fermat's little theorem: For prime p and integer a not divisible by p, a^(p−1) is congruent to 1 modulo p. Its prime-number conclusion supplies the condition that Fermat pseudoprimes imitate.
Fermat liar: A base a coprime to composite n is a Fermat liar for n when a^(n−1) is congruent to 1 modulo n. Each base that accepts n as prime corresponds to a Fermat pseudoprime base.

Linked from 1 page