What are some examples of proof by contrapositive? Applying the Modus Tollens argument to Fermat's Little Theorem really helped me to understand logical implication. I never knew that FLT was actually a compositality test.
Theorem (FLT): given integers $a>1$ and $n>1$, if $n$ is prime, then $a^n$ is congruent to $a\  (\bmod\  n)$.
By the contrapositive, if $a^n$ is not congruent to $a\  (\bmod\  n)$, then $n$ is not prime. Thus $n$ is composite.

What are some other simple and instructive examples of proof by contrapositive?

 A: When you want to prove "If $p$ then $q$", and $p$ contains the phrase "$n$ is prime" you should use contrapositive or contradiction to work easily, the canonical example is the following:
Prove for $n>2$,

If $n$ is prime then $n$ is odd.

Here $q$ is the phrase "$n$ is odd". Here $p$ is exactly the phrase "$n$ is prime" and is very difficult to work with it.
Because the fact that $n$ is prime means that it is not divisible by other number grater than $1$ and different for $n$, so you must to choose from these $n-2$ true sentences the only one that is useful which is "$n$ is not divisible by 2", but you would not know which is the right choice, unless you read $q$.
But proving contrapositive equivalent form is very easy, and you don't to do any choice.

If $n$ is even then $n$ is not prime.

Which follows from the fact that every even number greater than $2$ is divisible by $2$, hence not prime.
So contrapositive (also contradiction) is used to avoid situations where you have a lot of information and very little of it is actually useful.
A: Look at Richard Hammack's "Book of Proof" for a detailed discussion of proof forms. There are several "proof technique" and such introductory courses (perhaps under discrete mathematics and similar) with lecture notes on the 'net. 
