CMSC 250 Fall 2001 Homework 6 solutions

The truth set for the situations will be:
1. Proof (by contradiction): Assume: $(\frac{1}{r})^2 \leq \frac{1}{r}$
  $(\frac{1}{r})^2 \leq \frac{1}{r}$
  $\frac{1}{r^2} \leq \frac{1}{r}$
  $r^2 \cdot \frac{1}{r^2} \leq r^2 \cdot \frac{1}{r}$
  $1 \leq r$
  This is a contradiction to the original statement that .
  Since r can't be both and $\geq 1$ , the assumption that $(\frac{1}{r})^2 \leq \frac{1}{r}$ must be false.
  This means that it must be true that $(\frac{1}{r})^2 > \frac{1}{r}$ .
2. Counterexample: Let r be 1 and let s be an irrational number such as $\sqrt{2}$ . Then, which is irrational.
1. Want to show that $a\vert c$ . In other words, for some $k\in{\bf {Z}}$ . Proof: Since $a\vert b$ , for some $r\in{\bf {Z}}$ . Since $b\vert c$ , for some $s\in{\bf {Z}}$ . Hence, , so $a\vert c$ because $rs \in Z$ .
2. Counterexample: Let , . Then, $a\not \vert 8$ and $a \vert 8b$ , but $a\not \vert b$ .
Using div and mod notation, ,, and are defined by: h=num_seconds div 3600 m=(num_seconds div 60) mod 60 s=num_seconds mod 60
Floor and Ceiling Questions
1. Counterexample: Let . Then $\lceil x^3 \rceil = \lceil 1.728 \rceil = 2$ , and $(\lceil 1.2 \rceil)^3 = 2^{3} = 8$ ,
2. Counterexample: Let $x=0.1,\,\,y=1.2,\,\,z=2.4.$ Then $\lfloor x+y+z \rfloor = \lfloor 3.7\rfloor = 3$ , and $\lfloor .1 \rfloor + \lfloor 1.2 \rfloor + \lfloor 2.4 \rfloor = 0 + 1 + 2 = 6$ .
1. Proof by contraposition: We show that if is even, then $n^{3}+n^{2}+n$ is even. Proof: Let n=2k, for some $k\in{\bf {Z}}$ . Then, $(n^{3}+n^{2}+n) = (2k)^3+(2k)^2+(2k) = 8k^3+4k^2+2k = 2(4k^3+2k^2+k)$ . And $(4k^3+2k^2+k) \in Z$ because of closure over the integers. This means that $(n^{3}+n^{2}+n)$ can be written in the form for some $j\in{\bf {Z}}$ , so it is even.
2. By the Prime Factorization Theorem,
  $a = p^{e_a}a_1$ where $p \not \vert a_1$ and $e_a \in Z$ and $e_a \geq 0$
  $b = p^{e_b}b_1$ where $p \not \vert b_1$ and $e_b \in Z$ and $e_b \geq 0$
  Multiplying and as defined above we get
  $ab = (p^{e_a}a_1)(p^{e_b}b_1)$
  $ab = p^{e_a+e_b}a_1b_1$
  And $p\vert ab$ means
  
  ASSUME: $p \not \vert a \wedge p \not \vert b$
  $p\not \vert a$ means
  $p\not \vert b$ means
  This means that .
  That is a contradition to .
  THEREFORE the opposite of the assumption must be true which is that $p \vert a \vee p\vert b$ .
3. We want to show that for some $l\in{\bf {Z}}$ . Proof: Since $a\equiv b\hbox{ mod }n$ , for some $q\in{\bf {Z}}$ . Since $m\vert n$ , for some $k\in{\bf {Z}}$ . Hence, , so . Since is an integer, by the definition of congruence mod , $a\equiv b\hbox{ mod } m$ .
We want to determine all possible values for . Since $p\vert a$ , for some $r\in{\bf {Z}}$ . Since $p\vert a+q$ , for some $s\in{\bf {Z}}$ . Therefore, , which means that . Hence, $p\vert q$ . Since is prime, this means that must be 1 or . Since is prime, cannot be , so .
Proof by contradiction: Suppose that is an irriational number and $\sqrt[3]{s}$ is rational. Then, $\sqrt[3]{s}=\frac{a}{b}$ for some integers and with $b\neq 0$ . Hence, $(\sqrt[3]{s})^{3}=\frac{a^{3}}{b^{3}}$ . Since $a^{3}\in{\bf {Z}}$ and $b^{3}\in{\bf {Z}}$ and $b^{3}\neq 0$ since $b\neq 0$ , is a rational number. This is a contradiction, so $\sqrt[3]{s}$ is irrational.
Proof by contradiction: Suppose that $\sqrt{5}$ is rational. Then $\sqrt{5} = \frac{a}{b}$ for some integers and , where $b\neq 0$ . Then, $5 =\frac{a^{2}}{b^{2}}$ , which means that $5b^{2} =a^{2}$ . By the unique factorization theorem, $b=5^{k}b_{1}$ for some $k, b_{1}\in{\bf {Z}}$ , where $k\geq 0$ and $5\not \vert b_{1}$ , and $a=5^{l}a_{1}$ for some $l,a_{1}\in{\bf {Z}}$ , where $l\geq 0$ and $5\not \vert a_{1}$ . Hence, $5(5^{k}b_{1})^{2}=(5^{l}a_{1})^{2}$ , and $5^{2k+1}b_{1}^{2}=5^{2l}a_{1}^{2}$ , which means that because there is a unique factorization of the integer on the left and the right into a product of nonnegative powers of primes. Hence, , which means that $(k-l) = \frac{1}{2}$ . This is a contradiction because is an integer and $\frac{1}{2}$ is not an integer. Therefore, $\sqrt{5}$ is not a rational number.