Why Miller–Rabin instead of Fermat primality test?
The Rabin-Miller algorithm also tests, given a number $n$, whether $Z_n$ has a nontrivial root of Unity. 

Carmichael numbers pass the Fermat test (for every basis $a$), but for every Carmichael number $n$, there exist many numbers $a$ such that the test for unity roots fails on $a$ (that is, the sequence $a,2a,...,2^ra$ eventually displays a nontrivial root of unity).

Thus, we have the following:

For Fermat's test, if a composite number $n$ is not Carmichael, then the probability that the test will detect compositeness is at least $1/2$. However, the test will fail all Carmichael numbers.

For the Rabin-Miller test, every composite number will be detected with probability at least $1/2$. This means that the correctness probability is independent of the input (there are no "hard" inputs). This is what makes this algorithm stronger.