Question 10.16: Prove that for any integer p > 1, if p isn’t pseudoprime,...
Prove that for any integer p > 1, if p isn’t pseudoprime, then p fails the Fermat test for at least half of all numbers in Z^{+}_{p}.
Call a a witness if it fails the Fermat test for p; that is, if a^{p-1} \not\equiv 1 (mod p).
Let Z^{*}_{p} be all numbers in {1, . . . , p − 1} that are relatively prime to p. If p isn’t pseudoprime, it has a witness a in Z^{*}_{p}.
Use a to get many more witnesses. Find a unique witness in Z^{*}_{p} for each nonwitness. If d ∈ Z^{*}_{p} is a nonwitness, you have d^{p-1}\equiv 1 (mod p). Hence (da mod p)^{p-1} \not\equiv 1 and so da mod p is a witness. If d_{1} and d_{2} are distinct nonwitnesses in Z^{*}_{p}, then d_{1} a mod p \neq d_{2}a mod p. Otherwise, (d_{1}-d_{2}) a\equiv 0 (mod p), and thus (d_{1}-d_{2}) a = cp for some integer c. But d_{1} and d_{2} are in Z^{*}_{p}, and thus (d_{1}-d_{2})\lt p, so a= cp/ (d_{1}-d_{2}) and p have a factor greater than 1 in common, which is impossible because a and p are relatively prime. Thus, the number of witnesses in Z^{*}_{p} must be as large as the number of nonwitnesses in Z^{*}_{p}, and consequently at least half of the members of Z^{*}_{p} are witnesses.
Next, show that every member b of Z^{+}_{p} that is not relatively prime to p is a witness. If b and p share a factor, then b^{e} and p share that factor for any e \gt 0. Hence b^{p-1} \not\equiv 1 (mod p). Therefore, you can conclude that at least half of the members of Z^{+}_{p} are witnesses.