In: Advanced Math
(a) Let a > 1 be an integer. Prove that any composite divisor of a − 1 is a pseudoprime of base a.
(b) Suppose, for some m, than n divides a^(m − 1) and n ≡ 1 (mod m). Prove that if n is composite, then n is a pseudoprime of base a.
(c) Use (b) to give two examples pseudoprimes of base a with a = 2 and a = 3 (hint: take m = 2k to be an even number).
A pseudoprime is a probable prime (an integer that shares a property common to all prime numbers) that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy. Some sources use the term pseudoprime to describe all probable primes, both composite numbers and actual primes.