In short
Every implication "if P then Q" is logically equivalent to its contrapositive: "if \lnot Q then \lnot P." Proof by contrapositive exploits this equivalence — instead of proving the original statement, you prove the contrapositive by a direct proof. The technique is especially useful when the negation of the conclusion gives you something concrete to work with, while the hypothesis itself is vague or hard to manipulate.
Here is a statement to prove: "If n^2 is odd, then n is odd." Try the direct approach. Start with "n^2 is odd," meaning n^2 = 2k + 1 for some integer k. Now... what? You need to show n is odd, meaning n = 2m + 1 for some integer m. But extracting a clean expression for n from n^2 = 2k + 1 is not straightforward — taking square roots of 2k + 1 does not land you in a nice algebraic form.
Now flip the statement around. The contrapositive of "if n^2 is odd then n is odd" is: "if n is not odd then n^2 is not odd" — in other words, "if n is even then n^2 is even." And that is a statement you already know how to prove directly. You proved it in Mathematical Proof — Direct Proof: if n = 2k, then n^2 = 4k^2 = 2(2k^2), which is even.
That is the entire idea. The contrapositive version of the statement was easier to prove than the original, and proving it was enough, because the two versions are logically the same statement.
What a contrapositive is
Take an implication P \Rightarrow Q — "if P, then Q." The contrapositive is the statement \lnot Q \Rightarrow \lnot P — "if not Q, then not P."
Contrapositive
The contrapositive of the implication "if P then Q" is "if \lnot Q then \lnot P." An implication and its contrapositive are logically equivalent: they are both true or both false. Proving one is the same as proving the other.
The logical equivalence is not a theorem you need to prove from scratch — it follows directly from the truth table of implication. An implication P \Rightarrow Q is false only when P is true and Q is false. The contrapositive \lnot Q \Rightarrow \lnot P is false only when \lnot Q is true and \lnot P is false — that is, when Q is false and P is true. Same condition. So they fail in exactly the same situations, which means they are equivalent.
Here is the equivalence as a truth table:
| P | Q | P \Rightarrow Q | \lnot Q | \lnot P | \lnot Q \Rightarrow \lnot P |
|---|---|---|---|---|---|
| T | T | T | F | F | T |
| T | F | F | T | F | F |
| F | T | T | F | T | T |
| F | F | T | T | T | T |
Columns 3 and 6 are identical. The implication and its contrapositive always have the same truth value.
Do not confuse the contrapositive with the converse
The converse of "if P then Q" is "if Q then P." This is a different statement — it may be true or false independently of the original.
The contrapositive of "if P then Q" is "if \lnot Q then \lnot P." This is the same statement.
Mixing these up is one of the most common logical errors. Consider: "If it is raining, then the ground is wet." The converse is "If the ground is wet, then it is raining" — which is false (someone might have poured water). The contrapositive is "If the ground is not wet, then it is not raining" — which is true, and logically guaranteed by the original.
| Name | Statement | Equivalent to original? |
|---|---|---|
| Original | If P, then Q | — |
| Converse | If Q, then P | No |
| Inverse | If \lnot P, then \lnot Q | No |
| Contrapositive | If \lnot Q, then \lnot P | Yes |
The converse and the inverse are equivalent to each other (they are contrapositives of one another), but neither is equivalent to the original. The contrapositive is the only safe swap.
The proof technique
The method is clean:
To prove "if P then Q" by contrapositive:
- Write the contrapositive: "if \lnot Q then \lnot P."
- Assume \lnot Q.
- Use definitions and known results to derive \lnot P.
- Conclude that the contrapositive is true, and therefore the original implication is true.
Step 3 is a direct proof of the contrapositive. So proof by contrapositive is not a fundamentally new technique — it is a direct proof of a different (but equivalent) statement. The art is in recognising when the contrapositive version is easier to prove than the original.
When the contrapositive is easier
The contrapositive is typically easier when:
-
The hypothesis is hard to unpack, but the negation of the conclusion is concrete. "If n^2 is odd, then n is odd" — the hypothesis "n^2 is odd" gives you n^2 = 2k + 1, which is hard to extract n from. But the negation of the conclusion — "n is even" — gives you n = 2m, which is easy to square.
-
The conclusion involves a "not" or "no" that would be hard to prove directly. "If a \cdot b = 0, then a = 0 or b = 0" is often proved by contrapositive: "If a \neq 0 and b \neq 0, then a \cdot b \neq 0." The negation of "a = 0 or b = 0" is "a \neq 0 and b \neq 0" (by De Morgan's law), which is a much more useful starting point.
-
The implication goes from a "squared" or "higher power" condition to a "first power" condition. Squaring is easy; un-squaring is hard. Going backwards via the contrapositive — from "not first power" to "not squared" — often means squaring again, which is the easy direction.
The interactive figure below illustrates the equivalence. Choose a pair of truth values for P and Q by dragging the point, and watch both the original implication and the contrapositive evaluate in real time — they always agree.
Two worked examples
Example 1: Prove that if $n^2$ is even, then $n$ is even
Claim. For any integer n: if n^2 is even, then n is even.
The direct approach is awkward — "n^2 is even" gives n^2 = 2k, and extracting n from that requires a square root, which does not simplify cleanly. The contrapositive is much easier.
Step 1. Write the contrapositive.
The contrapositive of "if n^2 is even, then n is even" is: "if n is not even, then n^2 is not even" — that is, "if n is odd, then n^2 is odd."
Why: flipping both sides and negating. "Not even" and "odd" are the same thing for integers, so the contrapositive translates cleanly.
Step 2. Assume n is odd.
By definition, n = 2k + 1 for some integer k.
Why: the definition of odd gives you a concrete expression to compute with — the hypothesis of the contrapositive is more algebraically tractable than the hypothesis of the original.
Step 3. Compute n^2.
Why: expand using the identity (a + b)^2 = a^2 + 2ab + b^2, then factor to put the result in the form 2m + 1.
Step 4. Identify the form.
Set m = 2k^2 + 2k. Since k is an integer, m is an integer (closure of \mathbb{Z} under multiplication and addition). So n^2 = 2m + 1, which means n^2 is odd by definition.
Why: the conclusion of the contrapositive requires "n^2 is odd," which means n^2 = 2m + 1 for some integer m. You have produced exactly that form.
Step 5. Conclude.
The contrapositive "if n is odd, then n^2 is odd" has been proved directly. Since an implication and its contrapositive are logically equivalent, the original statement — "if n^2 is even, then n is even" — is also true. \square
Result. If n^2 is even, then n is even.
The contrapositive turned an awkward problem into a routine one. The original asks you to go from n^2 back to n (un-squaring); the contrapositive asks you to go from n to n^2 (squaring). Squaring is the easy direction, and the contrapositive gave you permission to use it.
Example 2: Prove that if $ab$ is odd, then both $a$ and $b$ are odd
Claim. For integers a and b: if ab is odd, then a is odd and b is odd.
Again, the direct approach is hard: "ab is odd" gives ab = 2k + 1, and extracting individual information about a and b from their product is not straightforward. The contrapositive is cleaner.
Step 1. Write the contrapositive.
The negation of "both a and b are odd" is "at least one of a, b is even" (by De Morgan's law: \lnot(A \land B) = \lnot A \lor \lnot B).
So the contrapositive is: "if a is even or b is even, then ab is even."
Why: De Morgan's law converts "not both odd" into "at least one even." The contrapositive now has a concrete algebraic hypothesis — one of the factors is a multiple of 2.
Step 2. Assume at least one of a, b is even.
Without loss of generality, suppose a is even. (The argument for b being even is identical by symmetry, since multiplication is commutative.) So a = 2m for some integer m.
Why: if either one is even, the argument works the same way because ab = ba. Picking a as the even one simplifies notation without losing generality.
Step 3. Compute ab.
Why: substitute the definition of even for a and factor. The product mb is just an integer multiplied by an integer — nothing complicated.
Step 4. Conclude that ab is even.
Since m and b are integers, mb is an integer (closure). So ab = 2(mb), which is even by definition.
Why: the conclusion of the contrapositive requires "ab is even," which means ab = 2t for some integer t. You have t = mb.
Step 5. Conclude the original.
The contrapositive — "if at least one of a, b is even, then ab is even" — has been proved directly. Since the contrapositive is logically equivalent to the original, the original statement — "if ab is odd, then both a and b are odd" — is also true. \square
Result. If ab is odd, then both a and b are odd.
The area model makes the logic visual: an even factor forces the product into two equal halves, so the product cannot be odd. The only way for the product to be odd is for both factors to resist this splitting — which means both must be odd.
Comparing the three techniques
You now have three proof techniques: direct, contradiction, and contrapositive. Here is a summary of when each one shines.
| Technique | Structure | Best for |
|---|---|---|
| Direct | Assume P, derive Q | When there is a clear algebraic path from P to Q |
| Contrapositive | Assume \lnot Q, derive \lnot P | When \lnot Q is more concrete than P (e.g., un-squaring vs. squaring) |
| Contradiction | Assume \lnot Q (or \lnot P), derive impossibility | When the conclusion is a negative statement, or neither direct nor contrapositive gives a clean path |
The contrapositive is a special case of contradiction. If you prove "if \lnot Q then \lnot P" directly, you have used the contrapositive. If, during a contradiction proof, the specific contradiction you derive is "P and \lnot P" (that is, the hypothesis both holds and doesn't hold), then you were effectively doing a contrapositive proof. The distinction is largely about which strategy you set out with.
A common heuristic: try direct first. If the hypothesis does not unpack into anything useful, try the contrapositive. If neither works, try contradiction.
Common confusions
-
"The contrapositive and the converse are the same thing." They are not. The converse of "if P then Q" is "if Q then P" — a different statement. The contrapositive is "if \lnot Q then \lnot P" — the same statement as the original. The converse may be false even when the original is true. "If n = 6 then n is even" is true. Its converse, "if n is even then n = 6," is false (take n = 4). Its contrapositive, "if n is odd then n \neq 6," is true.
-
"I need to prove both the statement and the contrapositive." No — proving either one is enough. They are logically equivalent; proving one automatically establishes the other. You never need to prove both.
-
"Proof by contrapositive always works." It always applies (every implication has a contrapositive), but it is not always easier. Sometimes the contrapositive is just as hard as the original, and a direct proof is the cleanest path. The contrapositive is a tool, not a magic trick — it helps when the negation of the conclusion is more concrete than the hypothesis.
-
"Negating 'a is odd and b is odd' gives 'a is even and b is even.'" No — by De Morgan's law, the negation of "A and B" is "not A or not B." So the negation of "both odd" is "at least one is even," not "both are even." This is a frequent error in contrapositive proofs and changes the structure of the argument.
-
"Proof by contrapositive is the same as proof by contradiction." They are related but distinct. The contrapositive proves the equivalent statement \lnot Q \Rightarrow \lnot P directly — no contradiction is needed. Proof by contradiction assumes the negation and derives an explicit impossibility. The contrapositive is cleaner when it works, because it avoids the detour through absurdity.
Going deeper
If you came here to learn the contrapositive technique and see how it compares to direct proof and contradiction, you have everything you need. The rest of this section is for readers who want to see the logical subtleties and connections to more advanced ideas.
Why the equivalence holds: a semantic argument
The truth-table argument above establishes the equivalence mechanically. Here is a more intuitive way to see it. The implication P \Rightarrow Q says: "there is no situation in which P is true and Q is false." The contrapositive \lnot Q \Rightarrow \lnot P says: "there is no situation in which \lnot Q is true and \lnot P is false" — that is, "there is no situation in which Q is false and P is true." Same condition, just stated from the other direction. The two sentences are describing the same forbidden zone in the truth table.
Biconditional proofs
When you need to prove "P if and only if Q" (written P \Leftrightarrow Q), you are proving two implications: P \Rightarrow Q and Q \Rightarrow P. You can use the contrapositive for either or both directions. A common strategy: prove P \Rightarrow Q directly and prove Q \Rightarrow P by contrapositive (or vice versa). The biconditional is established once both directions are done.
For example, "n is even if and only if n^2 is even" requires both:
- Forward: if n is even then n^2 is even (direct proof — proved in Mathematical Proof — Direct Proof).
- Backward: if n^2 is even then n is even (proved by contrapositive in this article's Example 1).
Both directions are now established, so the biconditional holds.
Contrapositive in set theory
In Sets — Introduction, you learned that A \subseteq B means "every element of A is in B" — formally, "if x \in A then x \in B." The contrapositive is: "if x \notin B then x \notin A." This is sometimes the easier way to prove a subset relation. If you can show that anything not in B is automatically not in A, the subset relation follows.
This idea extends to Relations: when you have an implication linking membership in one set to membership in another, the contrapositive gives you an alternative route that is sometimes the cleaner proof.
Contrapositive in number theory
Many results about primes and divisibility are naturally proved by contrapositive. A classic example: "if p is prime and p \mid ab, then p \mid a or p \mid b." The contrapositive is: "if p \nmid a and p \nmid b, then p \nmid ab." This version — saying that a prime that misses both factors misses the product — is sometimes the form that fits naturally into a larger argument. In Number Theory Basics, the interplay between direct proof, contrapositive, and contradiction becomes the main toolkit.
Where this leads next
The contrapositive completes the trio of basic proof techniques. With direct proof, contradiction, and contrapositive in hand, you have the tools for almost every result in introductory mathematics.
- Mathematical Proof — Direct Proof — the foundational technique. Contrapositive proofs are direct proofs, just applied to the flipped statement.
- Proof by Contradiction — the closely related technique that handles cases where even the contrapositive does not give a clean path.
- Mathematical Induction — a technique for proving statements about all positive integers, which often uses direct proof or contrapositive within individual steps.
- Logic and Propositions — the formal framework of implication, negation, and equivalence that makes the contrapositive valid.
- Relations — where implications about set membership and ordering are proved by all three techniques, and the contrapositive is especially useful for partial orders and equivalence relations.