# 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?

• This question has a nice example; see especially the discussion in my answer. This question and its answer are another, and this, this, and this should also be of interest. These are just a few that I could easily find. – Brian M. Scott May 27 '13 at 4:32
• Thanks everyone for all the great examples. Now, I've got plenty to study. It sure would be interesting to compare samples from each area of Mathematics, a "logic parallel". – cyclochaotic May 27 '13 at 15:33

## 2 Answers

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.

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.