HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
Valid Arguments and Methods of Proof
  1. 1Validating statements and arguments
  2. 2Direct proof, contrapositive and counterexample
  3. 3Proof by contradiction and by cases
  1. Mathematics
  2. /Valid Arguments and Methods of Proof
  3. /Proof by contradiction and by cases

Course 36.3·Lesson 3 of 3

Proof by contradiction and by cases

A proof by contradiction assumes the negation of the claim and reaches something impossible, so the claim must be true; this is how we show that 2\sqrt{2}2​

Lesson 3 of 3Show all lessonsHide
Valid Arguments and Methods of Proof
  1. 1Validating statements and arguments
  2. 2Direct proof, contrapositive and counterexample
  3. 3Proof by contradiction and by cases

Try the code and the simulations beside the lesson.

What you will be able to do

  • write a proof by contradiction;
  • prove that 2\sqrt{2}2​ is irrational and that there are infinitely many primes;
  • split a proof into cases that cover every possibility;
  • use the pigeonhole principle.

The idea of a proof by contradiction

A detective says: "Suppose the butler did it. Then he was in the kitchen at nine. But at nine he was on a train. That is impossible. So the butler did not do it."

A proof by contradiction works the same way.

  1. Assume that the claim is false.
  2. Reason correctly from that assumption.
  3. Reach a statement that is impossible, such as q∧∼qq \wedge \sim qq∧∼q.
  4. So the assumption was wrong, and the claim is true.

It works because a true assumption cannot lead, by valid steps, to a false statement.

The square root of 2 is irrational

Claim. 2\sqrt{2}2​ is not a rational number.

Proof.

  1. Suppose, for a contradiction, that 2=ab\sqrt{2} = \dfrac{a}{b}2​=ba​. Here aaa and bbb are whole numbers, b≠0b \ne 0b=0, and the fraction is in lowest terms.
  2. Squaring gives a2=2b2a^2 = 2b^2a2=2b2. So a2a^2a2 is even.
  3. If a2a^2a2 is even, then aaa is even. We proved this in the last lesson. Write a=2ca = 2ca=2c.
  4. Then 4c2=2b24c^2 = 2b^24c2=2b2, so b2=2c2b^2 = 2c^2b2=2c2. So b2b^2b2 is even, and bbb is even.
  5. Now aaa and bbb are both even, so the fraction was not in lowest terms. This contradicts step 1.
  6. So 2\sqrt{2}2​ is irrational.

There are infinitely many primes

Claim. There is no largest prime number.

Proof.

  1. Suppose there are only finitely many primes: p1,p2,…,pkp_1, p_2, \dots, p_kp1​,p2​,…,pk​.
  2. Let N=p1p2⋯pk+1N = p_1 p_2 \cdots p_k + 1N=p1​p2​⋯pk​+1.
  3. Dividing NNN by any pip_ipi​ leaves remainder 111. So no pip_ipi​ divides NNN.
  4. But N>1N > 1N>1, so NNN has a prime factor. That prime is not in the list.
  5. This contradicts step 1. So there are infinitely many primes.

NNN itself need not be prime. With the primes 2,3,52, 3, 52,3,5 and 777, N=211N = 211N=211, which is prime. The proof only needs a prime factor outside the list.

Proof by cases

Sometimes the possibilities split into a few cases. Prove the claim in each one. The cases must cover everything.

Claim. For every integer nnn, n2+nn^2 + nn2+n is even.

  • Case 1: nnn is even. Then n2+n=n(n+1)n^2 + n = n(n + 1)n2+n=n(n+1) has the even factor nnn.
  • Case 2: nnn is odd. Then n+1n + 1n+1 is even, so n(n+1)n(n + 1)n(n+1) is even.

Every integer is even or odd, so the claim is proved.

Claim. For every integer nnn, n2n^2n2 leaves remainder 000 or 111 on division by 333.

Every integer is 3k3k3k, 3k+13k + 13k+1 or 3k+23k + 23k+2.

  • (3k)2=3(3k2)(3k)^2 = 3(3k^2)(3k)2=3(3k2): remainder 000.
  • (3k+1)2=3(3k2+2k)+1(3k + 1)^2 = 3(3k^2 + 2k) + 1(3k+1)2=3(3k2+2k)+1: remainder 111.
  • (3k+2)2=3(3k2+4k+1)+1(3k + 2)^2 = 3(3k^2 + 4k + 1) + 1(3k+2)2=3(3k2+4k+1)+1: remainder 111.

So a number such as 3m+23m + 23m+2 is never a perfect square.

The pigeonhole principle

If more than kkk letters go into kkk boxes, some box gets at least two. The proof is a contradiction: if every box had at most one, there would be at most kkk letters.

The general form: if more than kqkqkq objects go into kkk boxes, some box gets at least q+1q + 1q+1.

Example. Among any 131313 people, two were born in the same month. There are 121212 months and 131313 people.

Practise with new numbers

Try it in Python

A computer cannot check every fraction, but it can search far. The program looks for whole numbers with a2=2b2a^2 = 2b^2a2=2b2 for bbb up to 100001000010000 and finds none, as the proof says. Then it checks the cases for squares on division by 333.

Read it first. Then run it. How close does the best fraction get to 2\sqrt{2}2​?

1. Change the search to a2=3b2a^2 = 3b^2a2=3b2. Does it find a solution?

2. Change the divisor in the second part from 333 to 444. Which remainders do squares leave now?

Common mistakes

  • Not stating the assumption. Begin with "Suppose, for a contradiction, that ...".
  • Assuming the wrong negation. The negation of "2\sqrt{2}2​ is irrational" is "2\sqrt{2}2​ is rational", written as a fraction in lowest terms.
  • Cases that miss something. "n>0n > 0n>0 and n<0n < 0n<0" forgets n=0n = 0n=0.
  • Thinking N=p1⋯pk+1N = p_1 \cdots p_k + 1N=p1​⋯pk​+1 is always prime. It need not be. It only has a prime factor outside the list.

Remember these

  • Contradiction: assume the claim is false, reach the impossible.
  • 2\sqrt{2}2​ is irrational; there are infinitely many primes.
  • Cases must cover every possibility.
  • More than kqkqkq objects in kkk boxes put q+1q + 1q+1 in some box.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

  1. What do you assume first, to prove "there is no smallest positive rational number" by contradiction?
  1. Prove by cases that n3−nn^3 - nn3−n is even for every integer nnn.
  1. Why does the proof that 2\sqrt{2}2​ is irrational need "lowest terms"?
  1. Is 3m+23m + 23m+2 ever a perfect square, for an integer mmm?
  1. A drawer has socks of 555 colours. How many must you take out to be sure of two of the same colour?

References

  • NCERT, Mathematics Textbook for Class XII, Part II, Appendix 1, Proofs in Mathematics.
  • Richard Hammack, Book of Proof, third edition, Chapter 6, Proof by Contradiction.

Enroll free in Valid Arguments and Methods of Proof

Every lesson is open to read. Enrolling also lets you:

  • Mark lessons done and carry on where you stopped.
  • Take the tests of this lesson and its course.
  • Count the course towards the certificate for its chapter.
No payment. You can leave at any time.

Problems (3)

Prove by contradiction that √3 is irrational…Hard · High School (11–12) · by StemPy Lab
Prove by contradiction that there are no integers a and b with 6a + 9b = 100…Advanced · High School (11–12) · by StemPy Lab
Prove by cases that for every integer n, n² leaves remainder 0 or 1 when divided by 3…Advanced · High School (11–12) · by StemPy Lab
That was the last lessonBack to the course: take the test
← Valid Arguments and Methods of Proof
← Direct proof, contrapositive and counterexampleNext →

Discussion (0)

Log in to join the discussion.

Loading…

is irrational and that there are infinitely many primes. A proof by cases splits the possibilities, for example even and odd
nnn
, or the remainders on division by
333
, and proves the claim in each case. The pigeonhole principle is a short proof by contradiction.
about 25 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.

Question Sets (1)

Arguments and Proofs: Think It Through10 questions · by StemPy Lab

Notes (1)

Valid Arguments and Methods of Proof: Quick RevisionNote · by StemPy Lab