Proof by Contradiction

Name:

Class:

Date:

Show your work for each problem.

1.
You want to prove by contradiction that $\sqrt{3}$ is irrational. What is the correct first line?
1. a)Assume $3$ is irrational
2. b)Assume $\sqrt{3}$ is rational
3. c)Assume $\sqrt{3} = 3$
4. d)Assume $\sqrt{3}$ is irrational
2.
What is the smallest number of people you need so that at least two of them are guaranteed to be born in the same month?
3.
Which statement is false for every truth value of $p$ , so that it is a contradiction?
1. a) $p \lor \neg p$
2. b) $p \land \neg p$
3. c) $p \Rightarrow p$
4. d) $\neg\neg p$
4.
Someone claims that $N = 100$ is the largest even number. Follow the proof to show the claim is false.
5.
In the proof that $\sqrt{2}$ is irrational, you square $\sqrt{2} = \frac{a}{b}$ and multiply by $b^2$ . You get $a^2 = k \cdot b^2$ . What is $k$ ?
6.
Show with the pigeonhole idea that in a group of 13 people, some birth month is shared.
7.
What is the correct negation of "Every prime number is odd"?
1. a)Every prime number is even
2. b)Every odd number is prime
3. c)No prime number is odd
4. d)At least one prime number is not odd
8.
You want to prove $x > 5$ by contradiction. What do you assume?
1. a) $x \le 5$
2. b) $x \ge 5$
3. c) $x \neq 5$
4. d) $x < 5$
9.
A box holds single gloves in 7 different colors. How many gloves must you take without looking to be sure that two have the same color?
10.
Use a calculator to show that $\sqrt{2}$ lies strictly between $1.4142$ and $1.4143$ , so it equals neither of them.
11.
Someone claims that $\frac{1}{1000}$ is the smallest positive rational number. Halve it as in the proof. Which smaller positive rational number do you get? Write it as a fraction.
12.
How many people guarantee that two of them have the same birthday (day and month), counting February 29 as a possible birthday?
13.
Run Euclid's proof with the list of primes $2, 3, 5$ : build $N = 2 \cdot 3 \cdot 5 + 1$ and check that no prime on the list divides it.
14.
In Euclid's proof, compute $N = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 + 1$ for the first five primes.
15.
With the primes $2, 3, 5, 7, 11, 13$ , Euclid's number is $N = 30031 = 59 \times 509$ , which is not prime. What does this mean for the proof?
1. a)The proof fails, because $N$ is not prime
2. b)There are only six primes
3. c) $N$ has prime factors that are not on the list, so the proof still works
4. d) $59$ is the largest prime
16.
Follow the proof that $\sqrt{2}$ is irrational. Assume $\sqrt{2} = \frac{a}{b}$ in lowest terms and fill in the numbers.
17.
Prove that $\sqrt{3}$ is irrational the same way. Assume $\sqrt{3} = \frac{a}{b}$ in lowest terms and fill in the numbers. Use the fact that if a prime divides $a^2$ , it divides $a$ .
18.
Run Euclid's proof with the primes $2, 3, 5, 7, 11, 13$ and find the prime factors of $N$ .