InitHEADmain

1 files changed, 188 insertions, 0 deletions

diff --git a/Homework/math4310/alg_structurs_1.org b/Homework/math4310/alg_structurs_1.org
new file mode 100644
index 0000000..ae92f51
--- /dev/null
+++ b/Homework/math4310/alg_structurs_1.org
@@ -0,0 +1,188 @@
+#+TITLE: Assignment One
+#+AUTHOR: Logan Hunt
+#+STARTUP: entitiespretty fold inlineimages latexpreview
+#+LATEX_HEADER: \noindent \notag \usepackage{ dsfont }
+
+* Section 1.1
+** Question 5
+By reforming the given expression to show $ca$ as a multiple of $q$ and some remainder:
+
+\begin{align}
+a = bq + r \\
+ca = (cb)q + (c)r
+\end{align}
+
+and that $0 \leq r < b \Rightarrow 0 \leq cr < cb$, Theorem 1.1 tells us that there is only one unique quotient:
+which is $q$, and the remainder is $(c)r$.
+
+** Question 7
+By Theorem 1.1, $a = bq + r, 0 \leq r \lt b$ implies that when b = 3, $a = 3q + r$ where $0 \leq r \lt b$,
+thus $a \in \mathds{Z} \Rightarrow a = 3q + r$ where $r \in {0,1,2}$.
+
+By squaring $a$, we have three options which simplify to the form $3k$ or $3k + 1$:
+1. $a^2 = (3q)^2 = 9q^2$ which is $3k \ni k = 3q^2$
+2. $a^2 = (3q + 1)^2 = 9q^2 + 3q + 1 = 3(3q^2 + q) + 1$ which is $3k + 1 \ni k = (3q^2 + q)$
+3. $a^2 = (3q + 2)^2 = 9q^2 + 6q + 4 = 3(3q^2 + 2q) + 4$ which is
+   $3l + 4 \ni l = (3q^2 + 2q)$ which is also $3l + 1 + 3 = 3(l+1) + 1$,
+   which again is $3k + 1 \ni k = l+1$
+
+** Question 8
+By Theorem 1.1, $a = bq + r, 0 \leq r \lt b$ implies that when b = 4, $a = 4q + r$ where $0 \leq r \lt b$,
+and thus $a = 4q + r$ and $r \in {0,1,2,3}$.
+
+Therefore we have four cases:
+
+1. $a = 4q$, and $a$ must be even which is invalid
+2. $a = 4q + 1$, and $4q + 1 = 2k + 1 \ni k = 2q$ which fits the definition of an odd number
+3. $a = 4q + 2$, thus $a$ must be even as $a = 2k \ni k = 2q + 1$
+4. $a = 4q + 3$, can be rewritten to $4q + 1 + 2$, which is odd: $2k + 1 \ni k = 2q + 1$
+
+And thus any odd number can be rewritten as $4q + 1$ or $4q + 3$.
+
+** Question 10
+The division of $a$ and $c$ by $n$ can each be represented by
+
+\begin{align}
+a = q_{a}n + r_a \\
+c = q_c_{}n + r_c
+\end{align}
+
+where $0 \le r_a < n$ and $0 \le r_c < n$ by Theorem 1.1, and we can subtract each side of the
+second equation from the first:
+
+\begin{align}
+a - c = (q_{a}n + r_a) - (q_c_{}n + r_c)
+\end{align}
+
+With this work now in hand, we will prove by showing that the conjecture is true both ways:
+
+For the first, we will suppose that $r_a = r_c$. Then, we find that
+\begin{align}
+a - c = n(q_a - q_c) \\
+a - c = nk
+\end{align}
+for some integer $k$.
+
+For the second, we will prove that if $a - c = nk$, when $a$ and $c$ are divided by $n$,
+they leave the same remainder $r$.
+
+From the work we did previously, and by substituting $a-c = nk$, we find that
+\begin{align}
+a - c = (q_{a}n + r_a) - (q_c_{}n + r_c) \\
+nk = (q_{a}n + r_a) - (q_{c}n + r_c) \\
+nk = n(q_a - q_c) + (r_a - r_c) \\
+n(k - q_a + q_c) = r_a - r_c
+\end{align}
+and thus $r_a - r_c$ is a multiple of $n$.
+
+From the inequalities produced previously by Theorem 1.1, if $r_a \geq r_c$ then $0 \le r_a - r_c < n$
+and $-n < r_c - r_a \leq 0$. Else if $r_c \geq r_a$ then $0 \leq r_c - r_a < n$ and $-n < r_a - r_c \leq 0$.
+
+By combining the two cases, it must be that $ -n < r_a - r_c < n $, and from the above fact that
+$r_a - r_c$ is a multiple of n, the only multiple of n in $(-n, n)$ is 0. Thus $r_a = r_c$.
+
+* Section 1.2
+** Question 1
+*** c
+1,  57 and 112 are co-prime
+** Question 3
+\begin{align}
+a | b \Rightarrow \exists n \in \mathds{Z} \ni an = b \\
+b | c \Rightarrow \exists m \in \mathds{Z} \ni bm = c \\
+(an)m = c \Rightarrow a | c
+\end{align}
+** Question 4
+*** a
+\begin{align}
+a | b \Rightarrow \exists n \in \mathds{Z} \ni an = b \\
+a | c \Rightarrow \exists m \in \mathds{Z} \ni am = c \\
+a | (b + c) \Rightarrow \exists l \in \mathds{Z} \ni al = b + c \\
+al = an + am \\
+b + c = a(n + m)
+\Rightarrow a | b+c
+\end{align}
+*** b
+By continuing from "a":
+
+\begin{align}
+br + ct = (an)r + (am)t \\
+\Rightarrow br + ct = a(nr + mt) \\
+\Rightarrow a | (br + ct)
+\end{align}
+
+
+** Question 7
+$|a|$ since $|a| \textbar a$ and $|a| \textbar 0$, and there cannot be an integer larger than
+$|a|$ that divides $a$.
+
+** Question 9
+No, not every multiple of two factors of an integer divides that integer.
+
+For example, $3 | 9$ and $9 | 9$ but $27 \nmid 9$.
+
+** Question 15
+*** c
+\begin{align}
+1003 = (2)(456) + 91 \\
+456 = (5)(91) + 1 \\
+91 = (91)(1) + 0 \\
+\Rightarrow (1003, 456) = 1
+\end{align}
+*** d
+\begin{align}
+322 = (2)(148) + 26 \\
+148 = (5)(26) + 18 \\
+26 = (1)(18) + 8 \\
+18 = (2)(8) + 2 \\
+8 = (4)(2) + 0 \\
+\Rightarrow (322, 148) = 2
+\end{align}
+
+** Question 17
+
+\begin{align}
+a | c \Rightarrow \exists n \in \mathds{Z} \ni an = c \\
+b | c \Rightarrow b | an
+\end{align}
+
+And by Theorem 1.4, $(a, b) = 1 \Rightarrow b | n \Rightarrow ab | an \Rightarrow ab | c$:
+
+** Question 19
+Given some $d$ such that $d | a$ and $d | b$, then $a = nd$ and $b = md$.
+\begin{align}
+a | (b + c) \Rightarrow \exists p \in \mathds{Z} \ni ap = b + c \\
+c = ap - md \Rightarrow c = (nd)p - md \Rightarrow c = d(np - md) \Rightarrow d | c
+\end{align}
+
+Since we're given that $(b, c) = 1 \Rightarrow (md, c) = 1$ and from the above fact that $d | c$, we can conclude
+that $md = 1$. Therefore $(a, b) = (a, md) = (a, 1) = 1$.
+
+Given some $e$ such that $e | a$ and $e | c$, then $a = ue$ and $c = we$.
+\begin{align}
+a | (b + c) \Rightarrow \exists o \in \mathds{Z} \ni ao = b + c \\
+b = ao - we \Rightarrow b = (ue)o - we \Rightarrow b = e(uo - w) \Rightarrow e | b
+\end{align}
+
+And from similar reasoning we can conclude that $(a, c) = (a, we) = (a, 1) = 1$.
+
+** Question 31
+*** a
+$[6, 10] = 60$
+
+$[4, 5, 6, 10] = 60$
+
+$[20, 42] = 840$
+
+$[2, 3, 14, 36, 42] = 252$
+
+*** b
+Let $m = [a_1, a_2, \ldots, a_k]$, then by the Division Algorithm, $t = mq + r$ for integers $q$ and $r$,
+with $0 \leq r < m$.
+
+As given that all $a_i | t$ \Rightarrow $a_i | mq + r$, and as $mq$ is a multiple of the LCM including
+a_i, $a_i$ must divide $mq$, and thus $a_i | r$.
+
+Because $a_i | r$, $r = na_i$ and is thus a multiple of all $a_i$, but the above statement that
+$0 \leq r < m$ shows that $m$ - the LCM by definition - is greater than $r$. Therefore, $r = 0$ and
+$t = mq \Rightarrow m | t$.
+