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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Brian M. Scott May 27 '13 at 4:32
  • $\begingroup$ 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". $\endgroup$ – cyclochaotic May 27 '13 at 15:33

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.