A strong pseudoprime is a composite number that passes the Miller–Rabin primality test.
Modulo a prime, the residue 1 can have no other square roots than 1 and minus 1.
For another example, pick n = 47197 and calculate in the same manner: In this case, the result continues to be 1 (mod 47197) until we reach an odd exponent.
Finally, consider n = 74593 where we get: Here, we reach minus 1 modulo 74593, a situation that is perfectly possible with a prime.
An odd composite number n = d · 2s + 1 where d is odd is called a strong (Fermat) pseudoprime to base a if: 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.
Guy mistakenly gives a definition with only the first condition, which is not satisfied by all primes.
The true probability of a failure is generally vastly smaller.
By judicious choice of bases that are not necessarily prime, even better tests can be constructed.