Question 10.16: Prove that for any integer p > 1, if p isn’t pseudoprime,...

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.