## Proof by Contradiction

The following is the list of problems for Chapter 6 of the Book of Proof (page 118). There is a forum open at the end, so you can ask questions. It is a great way to interact with the instructor and with other students in your class, should you need some assistance with any question. Please, do not post solutions.

A. Use the method of proof by contradiction to prove the following statements. (In each case, you should also think about how a direct or contrapositive proof would work. You will find in most cases that proof by contradiction is easier.)

1. Suppose $$n \in \mathbb{Z}$$. If $$n$$ is odd, then $$n^2$$ is odd.
2. Suppose $$n \in \mathbb{Z}$$. If $$n^2$$ is odd, then $$n$$ is odd.
3. Prove that $$\sqrt[3]{2}$$ is irrational.
4. Prove that $$\sqrt{6}$$ is irrational.
5. Prove that $$\sqrt{3}$$ is irrational.
6. If $$a, b \in \mathbb{Z}$$, then $$a^2-4b-2 \neq 0$$.
7. If $$a, b \in \mathbb{Z}$$, then $$a^2-4b-3 \neq 0$$.
8. Suppose $$a, b, c, \in \mathbb{Z}$$. If $$a^2 + b^2 = c^2$$, then $$a$$ or $$b$$ is even.
9. Suppose $$a, b \in \mathbb{R}$$. If $$a$$ is rational and $$ab$$ is irrational, then $$b$$ is irrational.
10. There exist no integers $$a$$ and $$b$$ for which $$21a + 30b = 1$$.
11. There exist no integers $$a$$ and $$b$$ for which $$18a + 6b = 1$$.
12. For every positive $$x \in \mathbb{Q}$$, there is a positive $$y \in \mathbb{Q}$$ for which $$y < x$$.
13. For every $$x \in [\pi/2, \pi]$$, $$\sin x - \cos x \geq 1$$.
14. If $$A$$ and $$B$$ are sets, then $$A \cap (B \setminus A) = \emptyset$$.
15. If $$b \in \mathbb{Z}$$ and $$b \!\nmid\! k$$ for every $$k \in \mathbb{N}$$, then $$b=0$$.
16. If $$a$$ and $$b$$ are positive real numbers, then $$a + b \geq 2 \sqrt{ab}$$.
17. For every $$n \in \mathbb{Z}$$, $$4 \!\nmid\! (n^2+2)$$.
18. Suppose $$a,b \in \mathbb{Z}$$. If $$4 \vert (a^2+b^2)$$, then $$a$$ and $$b$$ are not both odd.

B. Prove the following statements using any method from Chapters 4, 5 or 6.

1. The product of any five consecutive integers is divisible by 120. (For example, the product of 3, 4, 5, 6 and 7 is 2520, and $$2520=120 \cdot 21$$.)
2. We say that a point $$P = (x,y) \in \mathbb{R}^2$$ is rational if both $$x$$ and $$y$$ are rational. More precisely, $$P$$ is rational if $$P \in \mathbb{Q}^2$$. An equation $$F(x,y)= 0$$ is said to have a rational point if there exists $$x_0, y_0 \in \mathbb{Q}$$ such that $$F(x_0, y_0)=0$$. For ecample, the curve $$x^2+y^2-1=0$$ has rational point $$(x_0,y_0)=(1,0)$$. Show that the curve $$x^2+y^2-3=0$$ has no rational points.
3. Exercise 20 (above) involved showing that there are no rational points on the curve $$x^2+y^2-3$$. Use this fact to show that $$\sqrt{3}$$ is irrational.
4. Use the above result to prove that $$\sqrt{3^k}$$ is irrational for all odd, positive $$k$$.
5. The number $$\log_2 3$$ is irrational.