InitHEADmain

1 files changed, 135 insertions, 0 deletions

diff --git a/Homework/math4310/alg_structures_assn_2.org b/Homework/math4310/alg_structures_assn_2.org
new file mode 100644
index 0000000..d7dee4c
--- /dev/null
+++ b/Homework/math4310/alg_structures_assn_2.org
@@ -0,0 +1,135 @@
+#+TITLE: Assignment Two
+#+AUTHOR: Logan Hunt
+#+STARTUP: entitiespretty fold inlineimages
+#+LATEX_HEADER: \notindent \notag \usepackage{ dsfont } \usepackage{amsmath}
+#+LATEX: \setlength\parindent{0pt}
+
+
+* Section 1.3
+** Question 3
+701, 1009, 1949, 1951 are all prime
+** Question 7
+\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$.
+** Question 15
+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$.
+
+** Question 17
+
+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 \dots 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.
+
+** Question 30
+*** a
+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$!
+
+*** b
+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 2.1
+** Question 2
+*** a
+\begin{equation*}
+6k + 5 \equiv_4 6 + 5 \equiv_4 11 \equiv_4 3
+\end{equation*}
+
+*** b
+\begin{equation*}
+2r + 3s \equiv_{10} 2(3) + 3(-7) \equiv_{10} 6 - 21 \equiv_{10} -15 \equiv_{10} 5
+\end{equation*}
+
+** Question 3b
+\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
+
+** Question 5
+*** a
+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^{2000}] = [1] in $\mathds{Z}_4$.
+*** b
+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$.
+** Question 7
+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]}$
+
+** Question 14
+*** a
+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}
+
+*** b
+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$.
+
+