An odd composite number is a Fermat pseudoprime to a coprime base when
A Fermat pseudoprime is relative to its base. For example, passes base , but base yields , a Fermat witness. A Carmichael number has the stronger all-coprime-base property. This explains why finding one deceptive base and proving universal deception require different arguments.
Let be an odd integer that is a composite number and write with odd. For a base coprime to , it is a strong pseudoprime when
These are exactly the passing outcomes of the Miller-Rabin primality test for that base. The test computes by modular exponentiation and repeatedly squares it, looking for the permitted value before reaching exponent .
Every strong pseudoprime to a base is a Fermat pseudoprime to that base, by squaring a permitted congruence sufficiently many times. The converse fails. For , one has and , . Neither tested residue is , and the first is not , so base two detects compositeness even though .
Let for distinct odd prime numbers with . Exactly unit bases make a Fermat pseudoprime, and exactly of these make it a strong pseudoprime. The Fermat bases form under the Chinese remainder theorem for unit groups. If , then and is odd, so the th-power map sends five elements of each to and five to . The strong condition requires equal signs in both components, giving .

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.