\newlec

\hdc

Which of the following satisfies $x \equiv 40 \pmod{17}$\:?\\[2mm]

(Do not use a calculator.)\\[2mm]
 
\begin{enumerate}[A)]
\item $x=173$
\item $x=15^{5}+19^{3}-4$
\item $x=5\cdot18^{100}$
\item $x=2\cdot3\cdot5\cdot7\cdot11\cdot13$
\item $x=17^0+17^1+17^2+17^3+17^4+17^5+17^6$
\end{enumerate}

\vskip3em 
\soln \begin{enumerate}[A)]
\item $x=173 \equiv 3 \mod{17}$
\item $x=15^{5}+19^{3}-4 \equiv (-2)^{5} + 2^{3} - 4 \equiv -32 + 8-4 \equiv 2 + 4 \equiv 6 \mod{17}$
\item $x=5\cdot18^{100} \equiv 5(1)^{100} \equiv 5 \mod{17}$
\item $x=2\cdot3\cdot5\cdot7\cdot11\cdot13 \equiv 6\cdot 35 \cdot (-6)(-4) \equiv 6\cdot 1 \cdot 24 \equiv 6 \cdot 7 \equiv 42 \equiv 8 \mod{17}$
\item $x=17^0+17^1+17^2+17^3+17^4+17^5+17^6 \equiv 1 \mod{17}$
\end{enumerate}
Answer is the second option since $x \equiv 40 \equiv 6 \mod{17}$.

\ic{This is the 5-10 minute mark}

\newpage

\ic{Try to make the next exercise only take you to the 10 minute mark.}

\ex Show that there are no integer solutions to $x^{2} + 4y = 2$.
\vskip1em
\pf Assume towards a contradiction that there exist integers $x$ and $y$ such that $x^{2} + 4y = 2$. Reducing modulo $4$ yields $x^{2} \equiv 2 \mod{4}$. Trying all the possibilities yields
\begin{align*}
(0)^{2} &\equiv 0 \mod{4}\\
(1)^{2} &\equiv 1 \mod{4}\\
(2)^{2} &\equiv 0 \mod{4}\\
(3)^{2} &\equiv 1 \mod{4}
\end{align*}
Hence there are no integer solutions. \qed
\vskip1em
\note Notice that sometimes, you end up with many solutions. For example, $x^{2} \equiv 1 \mod{8}$ has $4$ solutions (all the odd numbers work! This is an exercise to check)
\vskip1em
\ic{ Now comes what I think is the hardest to grasp concept in this course; the abstraction of Z/mZ. I personally am going to discuss rings here and take a bit more time here to save a bit of time later on in the course. I will introduce the notion of a ring and field here so that when we get to complex numbers, it will go a bit quicker. This will cause me to spend more time here on topics but I think that's okay.}
\textbf{$\mathbb{Z}_{m}$ or $\mathbb{Z}/m\mathbb{Z}$ The integers modulo $m$}
\vskip1em
\defn The congruence or equivalence class modulo $m$ of an integer $a$ is the set of integers 
\[
[a] := \{x \in \mathbb{Z}: x \equiv a \mod{m}\}
\]
\note $:=$ means ``defined as''.
\vskip1em
Further, define
\[
\mathbb{Z}_{m} = \mathbb{Z}/m\mathbb{Z} := \{[0], [1], ... ,[m-1]\}
\]
\defn A commutative ring is a set $R$ along with two closed operations $+$ and $\cdot$ such that for $a,b,c \in R$ and 
\begin{enumerate}
\item Associative $(a + b) +c = a + (b + c)$ and $(ab)c = a(bc)$.
\item Commutative $a + b = b + a$ and $ab = ba$.
\item Identities: there are [distinct] elements $0,1 \in R$ such that $a + 0 = a$ and $a \cdot 1 = a$.
\item Additive inverses: There exists an element $-a$ such that $a + (-a) = 0$.
\item Distributive Property $a(b+c) = ab + ac$.
\end{enumerate}
\ex $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$. Not $\mathbb{N}$
\vskip1em
\defn If in addition, every nonzero element has a multiplicative inverse, that is an element $a^{-1}$ such that $a\cdot a^{-1} = 1$, we say that $R$ is a field.
\vskip1em
\ex $\mathbb{Q}$, $\mathbb{R}$. Not $\mathbb{N}$ or $\mathbb{Z}$.
\ic{This should take you tot he 25-30 minute mark}
\defn We make $\mathbb{Z}_{m}$ a ring by defining addition and subtraction and multiplication by $[a] \pm [b] := [a \pm b]$ and $[a]\cdot [b] := [ab]$. This makes $[0]$ the additive identity and $[1]$ the multiplicative identity.
\ic{Note that the $[a+b]$ means add then reduce modulo $m$. There is something subtle going on here that might be lost on students.}
There is one issue we need to resolve here; the issue of being well defined. How do we know that the above definition does not depend on the representatives chosen for $[a]$ and $[b]$?
\vskip1em
\ex For example, in $\mathbb{Z}_{6}$, is it true that $[2][5] = [14][-13]$? 
\ic{Note that $[2] = [14]$ and $[5] = [-13]$. To properly prove well-definedness, you would have to do this for all possible representations of $[a]$. Since this will create a notational disaster, I think it's best to try to illustrate the point with a concrete example.}
\pf Note that in $\mathbb{Z}_{6}$, we have
\[
\text{LHS} = [2][5] = [2\cdot5] = [10] = [4]
\]
and also
\[
\text{RHS} = [14][-13] = [14(-13)] = [-182] = [-2] = [4]
\]
completing the proof. \qed
\vskip1em
\defn The members $[0], [1], ... ,[m-1]$ are sometimes called representative members.
\ic{Minimum this is the 35 minute mark.}
\ic{In practice, this was the 50 minute mark but either way that's okay - hopefully you can squeeze in the addition table.}
Addition table for $\mathbb{Z}_{4}$
\begin{table}[ht!]
%\caption{default}
\begin{center}
\begin{tabular}{|c| c c c c|}
\hline
+ & $[0]$ & $[1]$ & $[2]$ & $[3]$ \\
\hline
$[0]$ & $[0]$ & $[1]$ & $[2]$ & $[3]$\\
$[1]$ & $[1]$ & $[2]$ & $[3]$ & $[0]$\\
$[2]$ & $[2]$ & $[3]$ & $[0]$ & $[1]$\\
$[3]$ & $[3]$ & $[0]$ & $[1]$ & $[2]$\\
\hline
\end{tabular}
\end{center}
%\label{default}
\end{table}%
