Failing Fermat Primality Test Consider the following algorithm:
Suppose $n\geq 2$, and let FermatTest be an algorithm such that if $a^{n-1}\not\equiv 1\mod n$ then return composite.  If FermatTest yields $a^{n-1}\equiv 1 \mod n$, then it returns possibly prime.
Let $n\geq 2$ be a composite integer that is not a Carmichael number.  Let $a \in \{1,2,\cdots n-1\}$. Why is it that if I randomly select $a$, there is a 1/2 chance that the test will say that it is composite.  I understand the group theoretic reason, but I was hoping for a number theoretic argument.
This question is inspired by this one here.
 A: Let $n$ be composite. Consider the $\varphi(n)$ numbers in the interval $1\le a\le n-1$ such that $a$ is relatively prime to $n$. 
Call such a number good if $a^{n-1}\not\equiv 1\pmod{n}$. So $a$ is good if using $a$ in the Fermat test we find that $n$ cannot be prime.  Let the set of good numbers be $G$. 
Call $a$ bad if it is not good, meaning that if we apply the Fermat primality test, we get the answer "possibly prime." Let the set of bad numbers be $B$.
We want to show that if $n$ is not a Carmichael number, then at least half of the $\varphi(n)$ numbers $a$ in our interval are good.  
Since $n$ is not a Carmichael number, there is a good number $g$.  Note that $gb$ is good for any bad number $b$. For 
$$(gb)^{n-1}=g^{n-1}b^{n-1}\equiv g^{n-1}\not\equiv 1\pmod{n}.$$
The values of $gb$ as $b$ ranges over $B$ are distinct modulo $n$. Thus there are at least as many good numbers as there are bad. This completes the argument. 
Remark: Let $n$ be composite but not Carmichael. The above result shows that even if $n$ is very large, repeated use of the Fermat Primality Test, with randomly chosen $a$, will, with probability close to $1$, quickly detect the compositeness. 
