%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Note to students! %
% %
% This source file is provided to give example LaTeX code. We do not recommend %
% trying to compile it, since it has some advanced LaTeX dependencies. %
% Specifically, this file depends on the cse311-common.cls file (link below) %
% and LuaLaTeX. The course staff will not be able to help much with %
% configuring your system for LuaLaTeX. %
% https://courses.cs.washington.edu/courses/cse311/21sp/section/cse311-common.cls
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[section, solutions]{../../latex-common/cse311-common}
\sectionnumber{05}
\topic{Number Theory}
\begin{document}
\maketitle
\section{GCD}
\begin{enumeratequestions}
\item Calculate gcd(100, 50).\\\\
\begin{solution}
50
\end{solution}
\item Calculate gcd(17, 31).\\\\
\begin{solution}
1
\end{solution}
\item Find the multiplicative inverse of 6 $\pmod{7}$.\\\\
\begin{solution}
6
\end{solution}
\item Does 49 have an multiplicative inverse $\pmod{7}$?\\\\
\begin{solution}
It does not. Intuitively, this is because 49x for any x is going to be 0 mod 7, which
means it can never be 1.
\end{solution}
\end{enumeratequestions}
\section{Extended Euclidean Algorithm}
\begin{enumeratequestions}
\item Find the multiplicative inverse $y$ of $7 \text{ mod } 33$. That is, find $y$ such that $7y \equiv 1 \pmod{33}$. You should use the extended Euclidean Algorithm.
Your answer should be in the range $0 \leq y < 33$.\\\\
\begin{solution}
First, we find the gcd:
\begin{align}
\gcd(33, 7) &= \gcd(7, 5) &\qquad 33 &= \fbox{7} \bullet 4 + 5\\
&= \gcd(5, 2) &\qquad 7 &= \fbox{5} \bullet 1 + 2\\
&= \gcd(2, 1) &\qquad 5 &= \fbox{2} \bullet 2 + 1\\
&= \gcd(1, 0) &\qquad 2 &= 1 \bullet 2 + 0\\
&= 1 &\qquad &
\end{align}
Next, we re-arrange equations (1) - (3) by solving for the remainder:
\begin{align}
1 &= 5 - \fbox{2} \bullet 2\\
2 &= 7 - \fbox{5} \bullet 1\\
5 &= 33 - \fbox{7} \bullet 4\\
\end{align}
Now, we backward substitute into the boxed numbers using the equations:
\begin{align*}
1 &= 5 - \fbox{2} \bullet 2\\
&= 5 - (7 - \fbox{5} \bullet 1) \bullet 2\\
&= 3 \bullet \fbox{5} - 7 \bullet 2\\
&= 3 \bullet (33 - \fbox{7} \bullet 4) - 7 \bullet 2\\
&= 33 \bullet 3 + 7 \bullet -14
\end{align*}
So, $1 = 33 \bullet 3 + \fbox{7} \bullet -14$. Thus, $33-14 = 19$ is the multiplicative inverse of $7 \text { mod }33$.
\end{solution}
\item Now, solve $7z\equiv 2(\text{mod }33)$ for all of its integer solutions $z$. \\\\
\begin{solution}
If $7y\equiv 1(\text{mod }33)$, then
$$ 2\cdot 7y\equiv 2(\text{mod }33).$$
So, $z\equiv 2\times 19(\text{mod }33)\equiv 5 (\text{mod }33)$.
This means that the set of solutions is $\{5+33k\mid k\in \mathbb Z \}$.
\end{solution}
\end{enumeratequestions}
\section{Euclid's Lemma\protect\footnote{these proofs aren't much longer than proofs you've seen so far, but it can be a
little easier to get stuck -- use these as a chance to practice how to get unstuck if you do!}}
\begin{enumeratequestions}
\item Show that if an integer $p$ divides the product of two integers $a$ and
$b$, and $\gcd(p, a) = 1$, then $p$ divides $b$.
\begin{solution}
Suppose that $p \mid ab$ and $\gcd(p, a) = 1$ for integers $a$, $b$, and $p$.
By Bezout's theorem, since $\gcd(p, a) = 1$, there exist integers $r$ and
$s$ such that
\begin{equation*}
rp + sa = 1.
\end{equation*}
Since $p \mid ab$, by the definition of divides
there exists an integer $k$ such that $pk = ab$.\\
By multiplying both sides of $rp + sa = 1$ by $b$ we have,
\begin{align*}
rpb + s(ab) &= b\\
rpb + s(pk) &= b\\
p(rb + sk) &= b
\end{align*}
Since $r$, $b$, $s$, $k$ are all integers, $(rb + sk)$ is also an integer.
By definition we have $p \mid b$.
\end{solution}
\item Show that if a prime $p$ divides $ab$ where $a$ and $b$ are
integers, then $p \mid a$ or $p \mid b$.
(Hint: Use part (a))
\begin{solution}
Suppose that $p \mid ab$ for prime number $p$ and integers $a$, $b$.
There are two cases.
Case 1: $\gcd(p, a) = 1$\\
In this case, $p \mid b$ by part (a).
Case 2: $\gcd(p, a) \neq 1$\\
In this case, $p$ and $a$ share a common positive factor greater than $1$.
But since $p$ is prime, its only positive factors are $1$ and $p$, meaning
$\gcd(p, a) = p$. This says $p$ is a factor of $a$, that is, $p \mid a$.
In both cases we've shown that $p \mid a$ or $p \mid b$.
\end{solution}
\end{enumeratequestions}
\end{document}