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.
$\endgroup$ 2What are some other simple and instructive examples of proof by contrapositive?
2 Answers
$\begingroup$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.
$\endgroup$ $\begingroup$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.
$\endgroup$
