Exercises

Exercises 3.4 Exercises

1.

Let \(n\) be an integer. Prove that if \(n\) is even, then \(n^2+2n+3\) is odd.

2.

Let \(n\) be an integer. Prove that if \(n\) is odd, then \(2n^2+9n+1\) is even.

3.

Prove that if \(8\) divides \(n\text{,}\) then \(4\) divides \(6n^2+5n+12\text{.}\)

4.

Prove that if \(3\) divides \(n\text{,}\) then \(3\) divides \(n^2+2n+6\text{.}\)

5.

Prove that if \(4\) divides \(n\text{,}\) then \(8\) divides \(2n^2 + n^3\text{.}\)

6.

Prove that if \(2n^2+7n\) is even and \(n\) is an integer, then \(n\) is even.

7.

Let \(n\) be an integer. Prove that if \(5n^2+2n+1\) is even, then \(n\) is odd.

8.

Let \(n\) be an integer. Prove that \(n\) is odd if and only if \(3n^2-7\) is even.

9.

Let \(n\) be an integer. Prove that \(n\) is even if and only if \(7n^2-4n+3\) is odd.

10.

Prove that the sum of two integers is odd if and only if one is even and the other is odd.

11.

Prove that if \(n\) is an integer, then \(n^2-n\) is even.

Hint.

Hint: There are two ways to approach this proof. The most straightforward given your toolset so far is a proof by cases: show that \(n^2-n\) is even if \(n\) is odd, and again if \(n\) is even. The more subtle alternate approach is to use the fact that \(n-1\) is odd if and only if \(n\) is even.

12.

Let \((a,b,c)\) be a Pythagorean triple, which is a triple of integers that satisfies the relationship \(a^2 + b^2 = c^2\text{.}\) Prove by contradiction that \(a\) and \(b\) cannot both be odd.

Solution.

Solution: Let \(a\text{,}\) \(b\text{,}\) and \(c\) be integers satisfying the Pythagorean relationship \(a^2+b^2=c^2\text{.}\) Assume for the sake of contradiction that \(a\) and \(b\) are both odd. In that case there exist integers \(k\) and \(m\) where \(a=2k+1\) and \(b=2m+1\text{.}\)

We will proceed by cases. Suppose \(c\) is odd, so there is an integer \(n\) where \(c=2n+1\text{.}\) Therefore,

\begin{align*} a^2 + b^2 \amp = c^2\\ (2k+1)^2 + (2m+1)^2 \amp = (2n+1)^2\\ 4k^2+4k+1 + 4m^2+4m+1 \amp = 4n^2+4n+1\\ 4k^2+4k+4m^2+4m+2-4n^2-4n \amp = 1\\ 2(2k^2+2k+2m^2+2m+1-2n^2-2n) \amp = 1 \end{align*}

We have proven \(1\) is even, which is contradictory.

In the other case, suppose \(c\) is even. Let there be an integer \(n\) where \(c=2n\text{.}\)

\begin{align*} a^2 + b^2 \amp = c^2\\ (2k+1)^2 + (2m+1)^2 \amp = (2n)^2\\ 4k^2+4k+1 + 4m^2+4m+1 \amp = 4n^2\\ 2 \amp = 4n^2 - 4k^2 - 4k - 4m^2 - 4m\\ 1 \amp = 2n^2 - 2k^2 - 2k - 2m^2 - 2m\\ 1 \amp = 2(n^2-k^2-k-m^2-m) \end{align*}

Again, we have shown \(1\) to be even. Since \(c\) is unable to be either even or odd, we must conclude that \(a\) and \(b\) cannot both be odd.

13.

Prove that \(\sqrt{3}\) is irrational by contradiction.

Hint.

Hint: Once you arrive at the claim that \(3q^2=p^2\) then if \(p\) is even then \(q\) will be, and vice-versa (make sure you understand why). So, they have to both be odd. But then what happens?

14.

Prove \(a|a\) for all nonzero integers \(a\text{.}\)

Hint.

Hint: Find an integer \(m\) such that \(a=am\) and then you're done.

15.

Prove that if there exist nonzero integers \(a\text{,}\) \(b\text{,}\) and \(c\) such that \(a|b\) and \(b|c\) then \(a|c\text{.}\)

Solution.

Solution: Suppose \(a\text{,}\) \(b\text{,}\) and \(c\) are nonzero integers such that \(a|b\) and \(b|c\text{.}\) Since \(a|b\) there exists an integer \(m\) such that \(b=am\text{,}\) and since \(b|c\) there exists an integer \(k\) such that \(c=bk\text{.}\) In that case,

\begin{align*} c \amp = bk\\ \amp = (am)k\\ \amp = a(mk) \end{align*}

Because we can write \(c\) as an integer times \(a\text{,}\) we have proven \(a|c\text{.}\)

16.

Let \(A\) and \(B\) be sets. Prove DeMorgan’s law for unions: \(\overline{A \cup B} = \overline{A} \cap \overline{B}\text{.}\)

Hint.

Hint: It's in the name.

Solution.

Solution: Let \(A\) and \(B\) be sets. Suppose \(x \in \overline{A \cup B}\text{.}\) By definition, \(x\) is not in either \(A\) or \(B\text{.}\) Equivalently, that means that \(x\) is not in \(A\) and also \(x\) is not in \(B\text{,}\) so \(x \in \overline{A} \cap \overline{B}\text{.}\) Because the element \(x\) was chosen arbitrarily we may conclude \(\overline{A \cup B} \subseteq \overline{A} \cap \overline{B}\text{.}\)

Conversely, let \(x \in \overline{A} \cap \overline{B}\text{.}\) That means that \(x\) is not in \(A\) and simultaneously \(x\) is not in \(B\text{,}\) which is the same as saying that \(x\) is not in \(A\) or in \(B\text{.}\) Therefore, \(x \in \overline{A \cup B}\text{,}\) which implies that \(\overline{A} \cap \overline{B} \subseteq \overline{A \cup B}\text{.}\)

Because we have shown the sets to contain each other, \(\overline{A} \cap \overline{B} = \overline{A \cup B}\text{.}\)

17.

Let \(A\) and \(B\) be sets. Prove DeMorgan’s law for intersections: \(\overline{A \cap B} = \overline{A} \cup \overline{B}\text{.}\)