Non-Conditional Statements

The following is the list of problems for Chapter 7 of the Book of Proof (page 129). 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.

Prove the following statements. These exercises are cumulative, covering all techniques addressed in Chapters 4–7.

1. Suppose \( x \in \mathbb{Z}. \) Then \( x \) is even if and only if \( 3x+5 \) is odd.
2. Suppose \( x in \mathbb{Z}. \) Then \( x \) is odd if and only if \( 3x+6 \) is odd.
3. Given an integer \( a, \) then \( a^3+a^2+a \) is even if and only if \( a \) is even.
4. Given an integer \( a, \) then \( a^2+4a+5 \) is odd if and only if \( a \) is even.
5. An integer \( a \) is odd if and only if \( a^3 \) is odd.
6. Suppose \( x, y \in \mathbb{R}. \) Then \( x^3+x^2y=y^2+xy \) if and only if \( y=x^2 \) or \( y=-x. \)
7. Suppose \( x, y \in \mathbb{R}. \) Then \( (x+y)^2=x^2+y^2 \) if and only if \( x=0 \) or \( y=0. \)
8. Suppose \( a, b \in \mathbb{Z}. \) Prove that \( a \equiv b \pmod{10} \) if and only if \( a \equiv b \pmod{2} \) and \( a \equiv b \pmod{5}. \)
9. Suppose \( a \in \mathbb{Z}. \) Prove that \( 14 \vert a \) if and only if \( 7 \vert a \) and \( 2 \vert a. \)
10. If \( a \in \mathbb{Z}, \) then \( a^3 \equiv a \pmod{3}. \)
11. Suppose \( a,b \in \mathbb{Z}. \) Prove that \( (a-3)b^2 \) is even if and only if \( a \) is odd or \( b \) is even.
12. There exists a positive real number \( x \) for which \( x^2 < \sqrt{x}. \)
13. Suppose \( a, b \in \mathbb{Z}. \) If \( a+b \) is odd, then \( a^2+b^2 \) is odd.
14. Suppose \( a \in \mathbb{Z}. \) Then \( a^2 \vert a \) if and only if \( a \in { -1, 0 1 } \).
15. Suppose \( a, b \in \mathbb{Z}. \) Prove that \( a+b \) is even if and only if \( a \) and \( b \) have the same parity.
16. Suppose \( a, b \in \mathbb{Z}. \) If \( ab \) is odd, then \( a^2+b^2 \) is even.
17. There is a prime number between 90 and 100.
18. There is a set \( X \) for which \( \mathbb{N} \in X \) and \( \mathbb{N} \subseteq X \).
19. If \( n \in \mathbb{N}, \) then \( 2^0 + 2^1 + 2^2 + \dotsb + 2^n = 2^{n+1}-1. \)
20. There exists \( n \in \mathbb{N} \) for which \( 11 \vert (2^n-1). \)
21. Every real solution of \( x^3+x+3=0 \) is irrational.
22. If \( n \in \mathbb{Z}, \) then \( 4 \vert n^2 \) or \( 4 \vert (n^2-1). \)
23. Suppose \( a, b \) and \( c \) are integers. If \( a \vert b \) and \( a \vert (b^2-c), \) then \( a \vert c. \)
24. If \( a \in \mathbb{Z}, \) then \( 4 \!\nmid\! (a^2-3). \)
25. If \( p > 1 \) is an integer and \( n \!\nmid\! p \) for each integer for which \( 2 \leq n \leq \sqrt{p}, \) then \( p \) is prime.
26. The product of any \( n \) consecutive positive integers is divisible by \( n!. \)
27. Suppose \( a, b \in \mathbb{Z}. \) If \( a^2 + b^2 \) is a perfect square, then \( a \) and \( b \) are not both odd.
28. Prove the division algorithm. If \( a, b \in \mathbb{N}, \) there exist unique integers \( q, r \) for which \( a = bq + r, \) and \( 0\leq r < b. \)
29. If \( a \vert bc \) and \( \gcd(a,b) = 1, \) then \( a \vert c. \) (suggestion: use the proposition in page 126)
30. Suppose \( a, b, p \in \mathbb{Z} \) and \( p \) is prime. Prove that if \( p \vert ab \) then \( p \vert a \) or \( p \vert b \). (suggestion: use the proposition in page 126)
31. If \( n \in \mathbb{Z}, \) then \( \gcd(n,n+1) = 1 \).
32. If \( n \in \mathbb{Z}, \) then \( \gcd(n,n+2) \in { 1, 2 }. \)
33. In \( n \in \mathbb{Z}, \) then \( \gcd(2n+1, 4n^2+1)=1. \)
34. If \( \gcd(a,c)=\gcd(b,c)=1, \) then \( \gcd(ab,c)=1. \) (suggestion: use the proposition in page 126).
35. Suppose \( a, b \in \mathbb{N}. \) Then \( a = \gcd(a,b) \) if and only if \( a \vert b. \)
36. Suppose \( a, b in \mathbb{N}. \) Then \( a = \lcm(a,b) \) if and only if \( b \vert a. \)