Therefore n − 1 is a sum of an even number of terms of the same parity so n − 1 must be even. It follows that 2p divides n − 1. Hence b^{2}^{p} − 1 is a divisor of b^{n-}^{1} − 1. However

Therefore n is a pseudoprime to the base b proving the theorem. □

Although there are infinitely many pseudoprimes they are not that common. It has been shown for example that there are only 21 853 pseudoprimes to the base 2 among the first 25 000 000 000 integers. Hence there is a good chance that if a number, especially a large number, passes a test as a pseudoprime, then it is really a prime. The question becomes how to make this chance, or probability, precise. Lists ...

Start Free Trial

No credit card required