Strong pseudoprime
In number theory, a probable prime is a number that passes a primality test. A strong probable prime is a number that passes a strong version of a primality test. A strong pseudoprime is a composite number that passes a strong version of a primality test. All primes pass these tests, but a small fraction of composites also pass, making them "false primes".
Unlike the Fermat pseudoprimes, for which there exist numbers that are pseudoprimes to all coprime bases (the Carmichael numbers), there are no composites that are strong pseudoprimes to all bases.
Formally, an odd composite number n = d · 2s + 1 with d also odd is called a strong (Fermat) pseudoprime to a relatively prime base a when one of the following conditions holds:
or
(If a number n satisfies one of the above conditions and we don't yet know whether it is prime, it is more precise to refer to it as a strong probable prime to base a. But if we know that n is not prime, then one may use the term strong pseudoprime.)
The definition is trivially met if a ≡ ±1 mod n so these trivial bases are often excluded.
Guy mistakenly gives a definition with only the first condition, which is not satisfied by all primes.
A strong pseudoprime to base a is always an Euler-Jacobi pseudoprime, an Euler pseudoprime and a Fermat pseudoprime to that base, but not all Euler and Fermat pseudoprimes are strong pseudoprimes. Carmichael numbers may be strong pseudoprimes to some bases—for example, 561 is a strong pseudoprime to base 50—but not to all bases.
...
Wikipedia