# HW3

## Part 1

### Set 4.2

28.

True.

Proof:

Suppose m and n are any two integers. We must show that if $n - m$ is even then $n^3 - m^3$ is even.

We consider all possible m and n combinations

(i) m and n are all odd

By definition of even and odd numbers, let $m=2k_1+1$, $n=2k_2+1$, where $k_1$ and $k_2$ are some integers.

$n - m = (2k_1+1) - (2k_2+1) = 2(k_1-k_2) = 2c_1$

Where c_1 is and integer since integers are closed under subtraction. By definition of even numbers, $n-m$ is even.

$$
\begin{align*}
n^3-m^3 &= (2k_1+1)^3 - (2k_2+1)^3\\
&= [(2k_1)^3+3(2k_1)^2+3(2k_1)+1] - [(2k_2)^3+3(2k_2)^2+3(2k_2)+1]\\
&= [8k_1^3+12k_1^2+6k_1+1] - [8k_2^3+12k_2^2+6k_2+1]\\
&= 8k_1^3+12k_1^2+6k_1 - 8k_2^3-12k_2^2-6k_2\\
&= 2(4k_1^3+6k_1^2+3k_1 - 4k_2^3-6k_2^2-3k_2)\\
&= 2c_2
\end{align*}
$$

Where c_2 is an integer since integers are closed under addition, subtraction, and multiplication. By definition of even numbers, $n^3-m^3$ is even.

(ii) m and n are all even

By definition of even numbers, let $m=2k_1$, $n=2k_2$, where $k_1$ and $k_2$ are some integers.

$n - m = 2k_1 - 2k_2 = 2(k_1-k_2) = 2c_1$

Where c_1 is and integer since integers are closed under subtraction. By definition of even numbers, $n-m$ is even.

$$
\begin{align*}
n^3-m^3 &= (2k_1)^3 - (2k_2)^3\\
&= 8k_1^3 - 8k_2^3\\
&= 2(4k_1^3-4k_2^3)\\
&= 2c_2
\end{align*}
$$

Where c_2 is an integer since integers are closed under subtraction and multiplication. By definition of even numbers, $n^3-m^3$ is even.

(iii) m is odd and n is even

By definition of even and odd numbers, let $m=2k_1+1$, $n=2k_2$, where $k_1$ and $k_2$ are some integers.

$n - m = (2k_1+1) - 2k_2 = 2(k_1-k_2) + 1 = 2c_1 + 1$

Where c_1 is and integer since integers are closed under subtraction. By definition of odd numbers, $n-m$ is odd. Therefore we need not to calculate $n^3-m^3$.

(iv) m is even and n is odd

By definition of even and odd numbers, let $m=2k_1$, $n=2k_2+1$, where $k_1$ and $k_2$ are some integers.

$n - m = 2k_1 - (2k_2+1) = 2(k_1-k_2-1) + 1 = 2c_1 + 1$

Where c_1 is and integer since integers are closed under subtraction. By definition of odd numbers, $n-m$ is odd. Therefore we need not to calculate $n^3-m^3$.

Combine (i), (ii), (iii), and (iv), we show that for all possible m and n combinations, if $n - m$ is even then $n^3 - m^3$ is even. Therefore, if $n - m$ is even then $n^3 - m^3$ is even.

36.

Suppose n is any integer. We must show that $(n+1)^2 - n^2$ is odd.

$$
\begin{align*}
(n+1)^2 - n^2 &= (n^2 + 2n + 1) - n^2\\
&= 2n+1
\end{align*}
$$

Since n is an integer, by definition of odd numbers, $(n+1)^2 - n^2$ is odd. Therefore, the difference of the squares of any two consecutive integers is odd.

+ Problem on canvas: Prove the statement "For any rational number s, $9s^4+\frac{3}{7}s−2$ is rational. (Use the definition of rational numbers, closure properties of integers, and the zero product property only to write down your proof. You will find a similar proof in the provided examples)

Suppose s is any rational number. We must show that $9s^4+\frac{3}{7}s−2$ rational.

By the definition of rational number, $\exists$ integers a, b such that $s = \frac{a}{b}$ and $b \ne 0$.

$$
\begin{align*}
9s^4+\frac{3}{7}s−2 &= 9(\frac{a}{b})^4+\frac{3}{7}(\frac{a}{b})−2\\
&= \frac{9a^4}{b^4} + \frac{3a}{7b} - 2\\
&= \frac{63a^4+3ab^3-14b^4}{7b^4}\\
&= \frac{p}{q}
\end{align*}
$$

p and q are both integers since a and b are integers and integers are closed under addition, subtraction, and multiplication.

Since $b \ne 0$ and $7 \ne 0$, $q = 7b^4 \ne 0$ by the zero product property.

Since p and q are both integers and $q \ne 0$, by the definition of rational numbers, $9s^4+37s−2$ is a rational number.

Therefore, for any rational number s, $9s^4+\frac{3}{7}s−2$ is rational.

### Set 4.3

39.

The proof assumes that $r+s$ is rational is true initially, which is what we want to prove. We cannot assume what we want to prove to be true initially.

Correct proof:

Suppose r and s are any two rational numbers. We must show that $r+s$ is also a rational number.

By the definition of rational numbers, $r = i/j$ and $s=m/n$ for some integers i, j, m, and n with $j \ne 0$ and $n \ne 0$.

$$
\begin{align*}
r + s &= \frac{i}{j} + \frac{m}{n}\\
&= \frac{in+jm}{jn}\\
&= \frac{a}{b}
\end{align*}
$$

a and b are both integers since integers are closed under addition and multiplication.

By the zero product property, since $j \ne 0$ and $n \ne 0$, $b = jn \ne 0$.

Because a and b are both integers and $b \ne 0$, $r + s$ is rational by definition.

Therefore, if r and s are any two rational numbers, then $r+s$ is also a rational number.

### Set 4.4

26.
True.

Proof:

Suppose a, b, and c are any integers. We must show that if $ab|c$ then $a|c$ and $b|c$.

By the definition of divisibility, we know that if $ab|c$, then $c=abn$ for some integer n.

Let $k_1=bn$. $k_1$ is an integer since integers are closed under multiplication.

$c=abn=ak_1$. By the definition of divisibility, $a|c$.

Let $k_2=an$. $k_2$ is an integer since integers are closed under multiplication.

$c=abn=ban=bk_2$. By the definition of divisibility, $b|c$.

Therefore, if $ab|c$ then $a|c$ and $b|c$.

+ Problem on canvas: Prove the statement- "For all integers a,b, and c if $a|b$ and $a|(b^2−c)$ , then $a|c$.

Suppose a, b, c are any integers. We must show that if $a|b$ and $a|(b^2−c)$, then $a|c$.

If $a|b$, by the definition of divisibility, $b=an$ for some integer n.

If $a|(b^2-c)$, by the definition of divisibility, $b^2-c=am$ for some integer m.

$c = b^2 - am = (an)^2 - am = a^2n^2-am=a(an^2-m)=ak$

k is an integer since a, n, m are all integers and integers are closed under multiplication and subtraction.

Since $c=ak$, by the definition of divisibility, $a|c$.

Therefore, for all integers a, b, and c, if $a|b$ and $a|(b^2−c)$, then $a|c$.

## Part 2

### Set 4.7

22.

The statement to prove is "For every real number r, if $r^2$ is irrational then r is irrational."

a. Proof by contradiction

To construct a proof by contradiction, assume that the original statement is not true, that means - "r is a real number such that $r^2$ is irrational and r is rational"

Our goal is to show that the supposition leads to a contradiction.

Since r is rational, by the definition of rational numbers, $r = a/b$ for some integers a, b with $b \ne 0$.

$r^2 = (\frac{a}{b})^2 = \frac{a^2}{b^2} = \frac{c}{d}$

Where c and d are both integers since integers are closed under multiplication.

By the zero product property, since $b \ne 0$, $d = b^2 \ne 0$.

Since $r^2 = \frac{c}{d}$ and both c and d are integers and $d \ne 0$, by the definition of rational numbers, $r^2$ is rational. Now, we have a contradiction that $r^2$ is rational and irrational.

That means the assumption is not correct. Therefore, the original statement is true.

b. Proof by contraposition

The contraposition of the original statement can be written as - "For every real number r, if r is rational then $r^2$ is rational"

Suppose that r is rational. We must show that $r^2$ is rational.

Since r is rational, by the definition of rational numbers, $r = a/b$ for some integers a, b with $b \ne 0$.

$r^2 = (\frac{a}{b})^2 = \frac{a^2}{b^2} = \frac{c}{d}$

Where c and d are both integers since integers are closed under multiplication.

By the zero product property, since $b \ne 0$, $d = b^2 \ne 0$.

Since $r^2 = \frac{c}{d}$ and both c and d are integers and $d \ne 0$, by the definition of rational numbers, $r^2$ is rational.

This proves the contraposition. So the original statement is also true.

27.

The statement to prove is "For all positive real numbers r and s, $\sqrt{r+s} \ne \sqrt{r} + \sqrt{s}$".

Proof by contradiction:

To construct a proof by contradiction, assume that the original statement is not true, that means - "Exists positive real numbers r and s such that $\sqrt{r+s} = \sqrt{r} + \sqrt{s}$"

We must show that the supposition leads to a contradiction.

We can take the square on the both side of the equation.

$$
\begin{align*}
&(\sqrt{r+s})^2 = (\sqrt{r} + \sqrt{s})^2\\
&\Rightarrow r+s = (\sqrt{r})^2 + (\sqrt{s})^2 + 2\sqrt{r}\sqrt{s}\\
&\Rightarrow r+s = r + s + 2\sqrt{rs}\\
&\Rightarrow 2\sqrt{rs} = 0\\
&\Rightarrow \sqrt{rs} = 0\\
&\Rightarrow (\sqrt{rs})^2 = 0^2\\
&\Rightarrow rs = 0
\end{align*}
$$

By the zero product property, since $r \ne 0$ and $s \ne 0$, $rs \ne 0$. Now, we have a contradiction that $rs = 0$ and $rs \ne 0$.

That means the assumption is not correct. Therefore, the original statement is true.

29.

The statement to prove is "For all integers m and n, if m + n is even then m and n are both even or m and n are both odd."

Proof by contraposition:
The contraposition of the original statement can be written as - "For all integers m and n, if one of m and n is even and the other is odd, then m + n is odd"

Without loss of generality, suppose that m is even and n is odd. We must show that $m + n$ is odd.

By definition of even numbers, $m = 2k_1$ for some integer $k_1$.
By definition of odd numbers, $n = 2k_2+1$ for some integer $k_2$.

$m + n = (2k_1) + (2k_2+1) = 2(k_1+k_2) + 1 = 2c+1$

c is integer since $k_1$ and $k_2$ are both integers and integers are closed under addition.

By the definition of odd numbers, $m + n$ is odd.

This proves the contraposition. So the original statement is also true.

### Problems on Canvas

+ Suppose x,y,z∈Z and x≠0 . Now use any indirect method to prove the statement "If x∤yz, then x∤y and x∤z."

The statement to prove is that "$x,y,z\in Z$ and $x \ne 0$. If x∤yz, then x∤y and x∤z."

Proof by contraposition:

The contraposition of the original statement can be written as - "$x,y,z\in Z$ and $x \ne 0$. If x|y or x|z then x|yz".

Suppose $x,y,z\in Z$ and $x \ne 0$. We must show that "If x|y or x|z then x|yz".

We consider the cases x|y and x|z.

(i) x|y

By the definition of divisibility, $y = ax$ for some integer a.

$yz = (ax)z = axz = xaz = x(az) = xb$

$b = az$ is an integer since a and z are integers and integers are closed under multiplicity.

Since $yz = xb$ and b is an integer, by the definition of divisibility, $x|yz$.

(ii) x|z

By the definition of divisibility, $z = cx$ for some integer c.

$yz = y(cx) = ycx = xyc = x(yc) = xd$

$d = yc$ is an integer since y and c are integers and integers are closed under multiplicity.

Since $yz = xd$ and d is an integer, by the definition of divisibility, $x|yz$.

Combine (i) and (ii) we know that if x|y or x|z then x|yz.
This proves the contraposition. So the original statement is also true.

+ Use any indirect method to prove the statement - "$\sqrt{6}$ is irrational" (Note: You can use Proposition 4.7.4 to prove this statement).

The statement to prove is "$\sqrt{6}$ is irrational".

Proof by contradiction:

To construct a proof by contradiction, assume that the original statement is not true, that means - "$\sqrt{6}$ is rational"
We must show that the supposition leads to a contradiction.

By the definition of rational numbers, $\sqrt{6} = a/b$ for some integers a and b with $b \ne 0$. Assume that a and b have no common factors.

$$
\begin{align*}
&\sqrt{6} = \frac{a}{b}\\
&\Rightarrow (\sqrt{6})^2 = (\frac{a}{b})^2\\
&\Rightarrow 6 = \frac{a^2}{b^2}\\
&\Rightarrow 6b^2 = a^2\\
&\Rightarrow a^2 = 6b^2 = 2(3b^2) = 2c
\end{align*}
$$

$c = 3b^2$ is integer since b is an integer and integers are closed under multiplication.

Since $a^2 = 2c$, by the definition of even numbers, $a^2$ is an even number.

By proposition 4.7.4, since $a^2$ is even, a is even.

By the definition of even numbers, $a = 2k$ for some integer k.

$$
\begin{align*}
&a^2 = 6b^2\\
&\Rightarrow (2k)^2 = 6b^2\\
&\Rightarrow 4k^2 = 6b^2\\
&\Rightarrow 2k^2 = 3b^2
\end{align*}
$$

Because integers are closed under multiplication, $k^2$ is an integer. By the definition of even numbers, $2k^2$ is even since $k^2$ is an integer. Therefore $3b^2$ is even. But 3 is odd, so $b^2$ must be even. By proposition 4.7.4, since $b^2$ is even, b is even.

Now, we have a contradiction that a and b have no common factors and a and b are both even (they have a common factor 2).

That means the assumption is not correct. Therefore, the original statement is true.