Fermat primality test for $a=n-1$

Question

If we want to know if $n$ is prime, we can do the Fermat primality test:

if $a^{n-1}\not\equiv 1 \mod n$, then $n$ is not prime.

Now I often find that we choose therefore $a\in\{2,\ldots, n-2\}$. Why not $a=n-1$? In Wikipedia, I found that for $a=n-1$ the congruence always holds. Why?

Answer 1

If $n$ is odd (usually, this is assumed) and $a=n-1$, then we have $$(n-1)^{n-1}\equiv (-1)^{n-1}=1\mod n;$$ hence the criterion is satisfied whenever $n$ is odd.

Answer 2

For $n>2$, $(n-1)^{n-1}=k(n).n+(-1)^{n-1}$ where $k(n)$ is given by the rest of the terms via the binomial expansion. Since all prime numbers greater than 2 are odd, $n-1$ is even for all cases of interest. So, one has $(n-1)^{n-1}\equiv1\ (mod\ n)$, for odd $n$. So, you don't have to check this case.

Answer 3

Computational expense, and as others have mentioned it works for any odd number in that case. If n is say 200 bits(25 bytes) long, it will Take 625 byte multiplies, and about the same number of byte additions with carries, Just to implement in Karatsuba multiplication ( for 1 increase in power). It doesn't take much overhead to make one method slower than another in certain ranges. About the only use for it if too slow for primality is the:$$a^{-1}\equiv a^{n-2} \pmod n$$ version of the test.