% Created 2023-01-18 Wed 12:13
% Intended LaTeX compiler: pdflatex
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\noindent \notag \usepackage{ dsfont }
\author{Logan Hunt}
\date{\today}
\title{Assignment One}
\hypersetup{
 pdfauthor={Logan Hunt},
 pdftitle={Assignment One},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={Emacs 28.2 (Org mode 9.5.5)}, 
 pdflang={English}}
\begin{document}

\maketitle
\tableofcontents


\section{Section 1.1}
\label{sec:org35f7eb6}
\subsection{Question 5}
\label{sec:orge503259}
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\).

\subsection{Question 7}
\label{sec:org6afde38}
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\):
\begin{enumerate}
\item \(a^2 = (3q)^2 = 9q^2\) which is \(3k \ni k = 3q^2\)
\item \(a^2 = (3q + 1)^2 = 9q^2 + 3q + 1 = 3(3q^2 + q) + 1\) which is \(3k + 1 \ni k = (3q^2 + q)\)
\item \(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\)
\end{enumerate}

\subsection{Question 8}
\label{sec:orgfe8a512}
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:

\begin{enumerate}
\item \(a = 4q\), and \(a\) must be even which is invalid
\item \(a = 4q + 1\), and \(4q + 1 = 2k + 1 \ni k = 2q\) which fits the definition of an odd number
\item \(a = 4q + 2\), thus \(a\) must be even as \(a = 2k \ni k = 2q + 1\)
\item \(a = 4q + 3\), can be rewritten to \(4q + 1 + 2\), which is odd: \(2k + 1 \ni k = 2q + 1\)
\end{enumerate}

And thus any odd number can be rewritten as \(4q + 1\) or \(4q + 3\).

\subsection{Question 10}
\label{sec:org3c66372}
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\textsubscript{a} - r\textsubscript{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{Section 1.2}
\label{sec:org4226083}
\subsection{Question 1}
\label{sec:org4ccc206}
\subsubsection{c}
\label{sec:org802af33}
1,  57 and 112 are co-prime
\subsection{Question 3}
\label{sec:orgb341781}
\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}
\subsection{Question 4}
\label{sec:orge55e932}
\subsubsection{a}
\label{sec:org7540edc}
\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}
\subsubsection{b}
\label{sec:orge72f7c4}
By continuing from "a":

\begin{align}
br + ct = (an)r + (am)t \\
\Rightarrow br + ct = a(nr + mt) \\
\Rightarrow a | (br + ct)
\end{align}


\subsection{Question 7}
\label{sec:org7273a90}
\(|a|\) since \(|a| \textbar a\) and \(|a| \textbar 0\), and there cannot be an integer larger than
\(|a|\) that divides \(a\).

\subsection{Question 9}
\label{sec:org6b4815b}
No, not every multiple of two factors of an integer divides that integer.

For example, \(3 | 9\) and \(9 | 9\) but \(27 \nmid 9\).

\subsection{Question 15}
\label{sec:orgf96c6cd}
\subsubsection{c}
\label{sec:orgad14e2b}
\begin{align}
1003 = (2)(456) + 91 \\
456 = (5)(91) + 1 \\
91 = (91)(1) + 0 \\
\Rightarrow (1003, 456) = 1
\end{align}
\subsubsection{d}
\label{sec:orgf89fea4}
\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}

\subsection{Question 17}
\label{sec:org66d011a}

\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\):

\subsection{Question 19}
\label{sec:org905b244}
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\).

\subsection{Question 31}
\label{sec:orgc12b666}
\subsubsection{a}
\label{sec:org4312735}
\([6, 10] = 60\)

\([4, 5, 6, 10] = 60\)

\([20, 42] = 840\)

\([2, 3, 14, 36, 42] = 252\)

\subsubsection{b}
\label{sec:orgb964c2c}
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\textsubscript{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\).
\end{document}