Difficulty: Intermediate | Prerequisites: Basic logic (AND, OR, NOT, implication), familiarity with even/odd integers and divisibility.
This material sits at the heart of discrete mathematics: learning to construct rigorous proofs. Proof by contradiction is one of the most widely used techniques in mathematics and computer science, and equivalence proofs (showing two statements imply each other) come up constantly in formal verification, algorithm correctness, and theory courses. You should already be comfortable with basic propositional logic and integer arithmetic. If you have not yet studied logical connectives and quantifiers, review those first.
Proof by contradiction works by assuming the opposite of what you want to prove, then showing that assumption leads to a logical impossibility. Equivalence proofs require you to prove both directions: A implies B, and B implies A. The classic example here is proving √3 is irrational (contradiction) and proving "n is even" is equivalent to "n³ + 1 is odd" (biconditional).
Proof by contradiction (reductio ad absurdum)
A proof technique where you assume the negation of the statement you want to prove, then derive a logical contradiction. The contradiction shows the original assumption must be false, so the statement must be true.
In simple terms, you say "suppose this were false," follow the logic, and show it blows up. That means it cannot be false.
Rational number
A number that can be expressed as a fraction a/b where a and b are integers and b ≠ 0.
Think of it as any number you can write as one whole number divided by another.
Irrational number
A number that cannot be expressed as a fraction of two integers. Its decimal expansion neither terminates nor repeats.
In simple terms, there is no fraction that equals this number exactly.
Coprime (relatively prime)
Two integers are coprime if their greatest common divisor is 1, meaning they share no prime factors.
Think of it as a fraction in its simplest, fully reduced form.
Equivalence proof (biconditional proof)
A proof that two statements are logically equivalent by proving both directions: if A then B, and if B then A.
In simple terms, you show each statement forces the other to be true.
Contrapositive
The contrapositive of "if P then Q" is "if not Q then not P." A statement and its contrapositive are always logically equivalent.
Think of it as flipping and negating both sides of an implication.
The goal is to prove that √3 cannot be written as a ratio of two integers.
Setup (assume the opposite)
Assume, for contradiction, that √3 is rational.
Then √3 = a/b for some integers a and b, where b ≠ 0 and a/b is fully reduced (a and b are coprime).
Derive the contradiction
Square both sides: 3 = a²/b², which gives 3b² = a².
Since a² = 3b², the number a² is divisible by 3. Because 3 is prime, a itself must be divisible by 3.
Write a = 3k for some integer k. Substitute back: 3b² = (3k)² = 9k², so b² = 3k².
Now b² is also divisible by 3, so b is divisible by 3.
Both a and b are divisible by 3, but we assumed they were coprime. Contradiction.
Conclusion
The assumption that √3 is rational leads to a contradiction. Therefore √3 is irrational.
Why this works (the structural pattern)
The technique relies on a key number-theoretic fact: if p is prime and p divides a², then p divides a. This same pattern can prove √2 or √5 irrational, just by swapping the prime.
To prove two statements are equivalent, you must prove both directions.
Forward direction: n is even → n³ + 1 is odd
Assume n is even, so n = 2k for some integer k.
Then n³ + 1 = (2k)³ + 1 = 8k³ + 1.
8k³ is even (it is 2 times 4k³), so 8k³ + 1 is odd.
Therefore n³ + 1 is odd. Direct proof, clean and done.
Reverse direction: n³ + 1 is odd → n is even (by contradiction)
Assume n³ + 1 is odd, but suppose (for contradiction) that n is odd.
If n is odd, write n = 2k + 1.
Then n³ + 1 = (2k + 1)³ + 1 = 8k³ + 12k² + 6k + 1 + 1 = 8k³ + 12k² + 6k + 2.
Factor: 2(4k³ + 6k² + 3k + 1). This is even.
But we assumed n³ + 1 is odd. Contradiction.
Therefore n must be even.
Why the reverse direction needs contradiction
The forward direction is a straightforward substitution. The reverse is harder to prove directly because starting from "n³ + 1 is odd" does not obviously lead to an expression for n. Contradiction sidesteps that by testing the only alternative (n is odd) and ruling it out.
\sqrt{3} = \frac{a}{b} \implies 3b^2 = a^2n = 2k \implies n^3 + 1 = 8k^3 + 1 \text{ (odd)}n = 2k+1 \implies n^3 + 1 = 2(4k^3 + 6k^2 + 3k + 1) \text{ (even)}Proof by contradiction is used throughout computer science to show that certain problems have no solution (e.g., the halting problem), that certain algorithms are optimal, or that security protocols cannot be broken under given assumptions. Equivalence proofs underpin formal verification, where engineers prove that a specification and its implementation describe the same behaviour.
Students often think that "assume a/b is in lowest terms" is optional in an irrationality proof. It is not. Without the coprimality assumption, you have no contradiction to reach.
Students sometimes try to prove an equivalence by showing only one direction. An equivalence (if and only if) always requires both directions.
A common error in the reverse direction of the equivalence proof is trying a direct proof instead of contradiction. Direct proofs from "n³ + 1 is odd" are awkward because cube roots of (odd number minus 1) do not simplify neatly.
Students occasionally confuse "proof by contradiction" with "proof by contrapositive." Contradiction assumes the negation and derives any absurdity. Contrapositive proves "if not Q then not P" as a direct proof, which is a narrower technique.
⚠️ Proof by contradiction is a near-certain exam topic. Know the structure cold: state the assumption, derive a contradiction, conclude.
⚠️ The √3 proof is a template. Expect variations like "prove √5 is irrational" or "prove √6 is irrational" using the same pattern.
⚠️ Equivalence proofs will appear as "show that A if and only if B" or "prove that A and B are equivalent." Always prove both directions.
⚠️ Know when to use direct proof versus contradiction. The forward direction of the equivalence (even → odd) was direct. The reverse used contradiction because the direct route was not clean.
True or false: To prove √3 is irrational, you start by assuming √3 is rational. True.
True or false: An equivalence proof only requires proving one direction. False. You need both.
Fill in the blank: If a² is divisible by a prime p, then a is ___ by p. Divisible.
True or false: If n is odd, then n³ + 1 is odd. False. If n is odd, n³ + 1 is even.
Fill in the blank: Two integers are coprime if their greatest common divisor is ___. 1.
Q: Outline the proof by contradiction that √3 is irrational.
A: Assume √3 = a/b with a, b coprime. Square both sides to get 3b² = a². Then a is divisible by 3, so write a = 3k. Substituting gives b² = 3k², so b is also divisible by 3. This contradicts coprimality, so √3 is irrational.
Q: Why does the proof that √3 is irrational require a and b to be coprime?
A: Without coprimality, the fact that both a and b are divisible by 3 is not a contradiction. Any fraction can be written with shared factors. The coprimality assumption creates the contradiction.
Q: Prove that if n is even, then n³ + 1 is odd.
A: Let n = 2k. Then n³ + 1 = 8k³ + 1. Since 8k³ is even, adding 1 makes it odd.
Q: What proof technique is used for the reverse direction (n³ + 1 odd → n even), and why?
A: Proof by contradiction. We assume n is odd and show n³ + 1 is even, contradicting the given. A direct proof is not straightforward from this starting point.
Q: Could you use the contrapositive instead of contradiction for the reverse direction?
A: Yes. The contrapositive of "n³ + 1 is odd → n is even" is "n is odd → n³ + 1 is even," which is a direct proof. Both contradiction and contrapositive work here.
Proof by contradiction connects directly to propositional logic (specifically the law of excluded middle and negation). If you go on to study computability theory, the proof that the halting problem is undecidable uses the same contradiction structure. Equivalence proofs reappear whenever you study logical equivalences, set equalities (showing A ⊆ B and B ⊆ A), or algorithm correctness (showing a loop invariant holds in both directions).
proof by contradiction, reductio ad absurdum, irrational numbers, √3 irrational proof, coprime integers, relatively prime, equivalence proof, biconditional, if and only if, iff, even odd parity, n cubed plus one, CS 182, Purdue, discrete mathematics, foundations of computer science, direct proof, contrapositive proof