#+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$.