Suppose n is a composite integer. Argue that there exists at least one integer a ∈ {1, 2, . . . , n − 1} such that a n−1 6≡n 1. (In other words, there’s always at least one nonzero a ∈ Zn with a n−1...

Suppose n is a composite integer. Argue that there exists at least one integer a ∈ {1, 2, . . . , n − 1} such that a
ⁿ⁻¹
6≡n 1. (In other words, there’s always at least one nonzero a ∈ Zn with a
ⁿ⁻¹
6≡n 1 when n is composite. Thus, although the probability of error in bogus-isPrime? from p. 742 may be very high for particular composite integers n, the probability of success is nonzero, at least!)

The following theorem is due to Alwin Korselt, from 1899: an integer n is a Carmichael number if and only if n is composite, squarefree, and for all prime numbers p that divide n, we have that p − 1 | n − 1. (An integer n is squarefree if there is no integer d ≥ 2 such that d²
| n.)