Fix an integer and an odd prime not dividing . Then
is a composite number that is a Fermat pseudoprime to base .
For compositeness, factor
Both factors are integers because is odd, and both exceed one for and . Also , so is coprime to .
By Fermat's little theorem, . Since is invertible modulo , this gives . The displayed sum is odd for either parity of , so . Finally , and raising this identity to the integer power proves .
For and , this produces and . The explicit restriction on matters: instead gives , which fails the base-two test.

Articles by others on the same topic (0)

There are currently no matching articles.