% Created 2023-01-25 Wed 08:50
% 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}
\notindent \notga \usepackage{ dsfont } \usepackage{amsmath}
\author{Logan Hunt}
\date{\today}
\title{Assignment Two}
\hypersetup{
 pdfauthor={Logan Hunt},
 pdftitle={Assignment Two},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={Emacs 28.2 (Org mode 9.5.5)}, 
 pdflang={English}}
\begin{document}

\maketitle
\tableofcontents

\setlength\parindent{0pt}


\section{Section 1.3}
\label{sec:orgb642b1a}
\subsection{Question 3}
\label{sec:orgefa83b9}
701, 1009, 1949, 1951 are all prime
\subsection{Question 7}
\label{sec:org19f664b}
\begin{align*}
p | a \Rightarrow np &= a \\
p | a + bc \Rightarrow mp &= a + bc \\
mp &= np + bc \\
mp - np &= bc \\
p(m - n) &= bc 
\end{align*}

Since \(bc\) is a multiple of \(p\), and \(p\) is prime, by Theorem 1.5, \(p | b\) or \(p | c\).
\subsection{Question 15}
\label{sec:orgec25485}
If \(p | a^n \Rightarrow p | a \cdot a \dotsc a\) then by corollary 1.6, \(p | a\). Then, \(a = pm\) and
\(a^n = p^n \cdot m^n\). \(p^n\) is a factor of \(a^n\) and thus \(p^n | a^n\).

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

From the Fundamental Theorem of Arithmetic, both \(a\) and \(b\) must be a product of primes such that
\(a = (p \cdot p_1 \cdot p_2 \dotsc p_i)\) and \(b = (p \cdot q_1 \cdot q_2 \dotsc q_j)\) with each \(p_i\) and \(q_j\) being prime.

Then, \(a^2 = (p \cdot p_1 \cdot p_2 \dotsc p_r) \cdot (p \cdot p_1 \cdot p_2 \dotsc p_r)\) and \(b^2 = (p \cdot q_1 \cdot q_2 \dotsc q_j) \cdot (p \cdot q_1 \cdot q_2 \dotsc q_j)\).
\(p^2\) is then a common factor of \(a^2\) and \(b^2\), and since each other factor (\(p_i^2\), \(q_i^2\)) is a square of a prime, there
can be no other greater common divisor than \(p^2\).

Therefore, \((a, b) = p \Rightarrow (a^2, b^2) = p^2\) when p is prime.

\subsection{Question 30}
\label{sec:org711c1fd}
\subsubsection{a}
\label{sec:org622b53c}
Firstly assume that there are \(a,b \ni a^2 = 2b^2\). Then, \(a^2 = p_1 p_2 \dotsc p_r\) and \(2b^2 = q_1 q_2 \dotsc q_s\),
and by the Fundamental Theorem of Arithmetic, every \(p_i = \pm q_j\). Since \(a^2\) is even as it is equal
to \(2b^2\), let \(p_1\) be the factor corresponding to a power of \(2\). Then \(p_1 = 2^n\) and \(n\) must be a
multiple of \(2\) since \(a^2 = 2^n \dotsc \Rightarrow a = 2^{\frac{n}{2}} \dotsc\)

However, \(2b^2 = \pm 2^n \dotsc\) implies that \(b^2 = \pm 2^{n-1} \dotsc\) and from similar reasoning \(n-1\) must also
be a multiple of \(2\).

This is a contradiction - not both \(n\) and \(n-1\) can be multiples of \(2\)!

\subsubsection{b}
\label{sec:orgfba7c43}
Just reformat it:

\begin{equation*}
\sqrt{2} = \frac{a}{b} \Rightarrow 2 = \frac{a^2}{b^2} \Rightarrow 2b^2 = a^2
\end{equation*}


\section{Section 2.1}
\label{sec:orgd42fe0f}
\subsection{Question 2}
\label{sec:org8c3b581}
\subsubsection{a}
\label{sec:orgc7b35b9}
\begin{equation*}
6k + 5 \equiv_4 6 + 5 \equiv_4 11 \equiv_4 3
\end{equation*}

\subsubsection{b}
\label{sec:org07ec8aa}
\begin{equation*}
2r + 3s \equiv_{10} 2(3) + 3(-7) \equiv_{10} 6 - 21 \equiv_{10} -15 \equiv_{10} 5
\end{equation*}

\subsection{Question 3b}
\label{sec:org29b1c99}
\begin{align*}
& 10(0) + 9(0) + 8(3) + 7(1) + 6(1) + 5(0) + 4(5) + 3(5) + 2(9) + 5 \\
&\equiv_{11 }24 + 7 + 6 + 20 + 15 + 18 + 5 \\
&\equiv_{11} 95 \\
&\equiv_{11} 7
\end{align*}

Invalid ISBN

\subsection{Question 5}
\label{sec:org37d83f3}
\subsubsection{a}
\label{sec:org770db68}
Theorem 2.2 states that if \(a \equiv_4 b\), and \(c \equiv_4 d\), then \(ac \equiv_4 bd\).

Since \(5 \equiv_4 1\) and \(5 \cdot 5 \equiv_4 1 \cdot 1\), then \(5 \cdot 5 \cdot 5 \equiv_4 1 \cdot 1 \cdot 1\).

We can continue chaining these together until we find \(5^{2000} \equiv_4 1^{2000}\), and thus [5\textsuperscript{2000}] = [1] in \(\mathds{Z}_4\).
\subsubsection{b}
\label{sec:org12acb79}
By repeating the same process as in a, \(4 \equiv_5 4\) and \(4^2 \equiv_5 1\). Then, \(4^3 \equiv_5 4 \cdot 1\). Then, \(4^4 \equiv_5 4^2 \Rightarrow 4^4 \equiv_5 1\).

In general as we keep chaining on and because of Theorem 2.2, even powers of 4 will be equivalent mod 5 to 1,
and odd powers of 4 will be equivalent mod 5 to 4.

Therefore, \(4^{2001} \equiv_5 1\) and \([4^{2001}] = [1]\) in \(\mathds{Z}_5\).
\subsection{Question 7}
\label{sec:orgc6a9940}
If \(a \in \mathds{Z}\) then \(a \equiv_4 m\) with \(m \in {1,2,3,4}\). Then, by Theorem 2.2 again, \(a^2 \equiv_4 m^2\).

\([m^2] \in \mathds{Z}_4\) must be equivalent to any \({[1^2], [2^2], [3^2], [4^2]} = {[1], [0], [1], [0]}\).

Therefore, \([a^2]\) cannot be in \({[3], [4]} \subset {[2], [3], [4]}\)

\subsection{Question 14}
\label{sec:org0f658a6}
\subsubsection{a}
\label{sec:org9ee67bf}
A simple python script will prove this is false:

\begin{verbatim}
seen = set()
for n in range(1, 10):
  for a in range(0, 10):
    for b in range(0, 10):
      seenfoo = (a, b, n) in seen or (b, a, n) in seen
      if (a * b) % n == 0 and a % n != 0 and b % n != 0 and not seenfoo:
        seen.add((a, b, n))
        print(f"a={a}, b={b}, n={n}")
\end{verbatim}

And we receive several counterexamples:

\begin{verbatim}
a=2, b=2, n=4
a=2, b=6, n=4
a=6, b=6, n=4
a=2, b=3, n=6
a=2, b=9, n=6
...
a=2, b=4, n=8
a=4, b=6, n=8
a=3, b=3, n=9
a=3, b=6, n=9
a=6, b=6, n=9
\end{verbatim}

\subsubsection{b}
\label{sec:org767f9d7}
If \(ab \equiv_n 0\), then \(ab = mn + 0\) for some \(m \in \mathds{Z}\) by definition.

Then, \(ab = mn\) implies that \(ab\) is a multiple of \(n\), and since \(n\) is prime, then by Theorem 1.8, \(n | ab\) implies that \(n | a\) or \(n | b\).
\end{document}