\newlec

\ic{An important announcement. Students should probably read the textbook but I anticipate most don't just due to timing restrictions. However, I would strongly advise students read Chapter 26 to get practice with the plethora of notation.}

\hdc

What is the last digit of $5^{32}3^{10} + 9^{22}$?
\vskip3em
\soln Want the remainder when we divide by $10$. Hence reduce modulo $10$ and use Congruent If and Only If Same Remainder.
\begin{align*}
5^{32} \cdot 3^{10} + 9^{22} &\equiv (5^{2})^{16}\cdot9^{5} + (-1)^{22} \mod{10}\\
&\equiv 5^{16}(-1)^{5} + 1 \mod{10}\\
&\equiv (5^{2})^{8}(-1) + 1 \mod{10}\\
&\equiv -5^{8} + 1 \mod{10}\\
&\equiv -(5^{2})^{4} + 1 \mod{10}\\
&\equiv -5^{4} + 1 \mod{10}\\
&\equiv -625  +1 \mod{10}\\
&\equiv -4 \mod{10}\\
&\equiv 6 \mod{10}
\end{align*}
Hence the last digit is $6$. \qed

\ic{This is the 10 minute mark.}
\newpage

\textbf{Linear Congruences}
\vskip1em
\qn Solve $ax \equiv c \mod{m}$ where $a,c \in \mathbb{Z}$ and $m \in \mathbb{N}$ for $x \in \mathbb{Z}$. 
\vskip1em
\note when we are solving $ax = c$ over the integers, we know that this has a solution if and only if $a \mid c$. 
\vskip1em
\ex Solve $4x \equiv 5 \mod{8}$. 
\vskip1em
\soln We associate a linear Diophantine equation to this linear congruence. By definition, there exists a $z \in \mathbb{Z}$ such that $4x - 5 = 8z$, that is, $4x- 8z = 5$. Now, letting $y = -z$. gives the linear Diophantine equation 
\[
4x + 8y = 5
\]
\ic{From now on I will jump straight to this version of the LDE without mentioning it so make sure they understand this change of variables trick to translate to an LDE quickly. This is why I go through this here.}
Since $\gcd(4,8) = 4 \nmid 5$, by LDET1, we see that this LDE has no solution. Hence the original congruence has no solutions. \qed
\vskip1em
\noindent \textbf{Solution 2:} Let $x \in \mathbb{Z}$. By the Division Algorithm, $x = 8q + r$ for some $0 \leq r \leq 7$ and $q,r$ integers. By Congruent If and Only If Same Remainder, $4x \equiv 5 \mod{8}$ holds if and only if $4r \equiv 5 \mod{8}$. Thus, if we can prove that no number from $0 \leq x \leq 7$ works, then no integer $x$ can satisfy the congruence. 
\ic{Again make a note that this explanation is not needed anymore to do these problems and is included here only for clarity.}
Trying the possibilities 
\begin{align*}
4(0) &\equiv 0 \mod{8}\\
4(1) &\equiv 4 \mod{8}\\
4(2) &\equiv 0 \mod{8}\\
4(3) &\equiv 4 \mod{8}\\
4(4) &\equiv 0 \mod{8}\\
4(5) &\equiv 4 \mod{8}\\
4(6) &\equiv 0 \mod{8}\\
4(7) &\equiv 4 \mod{8}
\end{align*}
shows that $4x \equiv 5 \mod{8}$ has no solution. \qed
\vskip1em
\noindent \textbf{Solution 3:} Assume towards a contradiction that there exists an integer $x$ such that $4x \equiv 5 \mod{8}$. Multiply both sides by $2$ to get (by Properties of Congruence) that
\[
0\equiv 0x \equiv 8x \equiv 10 \mod{8}
\]
Hence, $8 \mid 10$ however $8 \nmid 10$. This is a contradiction. Thus, there are no integer solutions to $4x \equiv 5 \mod{8}$. \qed
\ic{This is the 25 minute mark. Take your time with the previous argument. Encourage students to be creative with how they argue! If they find a solution encourage them to find another!}
\ex $5x \equiv 3 \mod{7}$.
\vskip1em
\soln Look Modulo $7$. Then there are only $7$ possibilities to consider for $x$. Trying them gives
\begin{align*}
5(0) &\equiv 0 \mod{7}\\
5(1) &\equiv 5 \mod{7}\\
5(2) &\equiv 3 \mod{7}\\
5(3) &\equiv 1 \mod{7}\\
5(4) &\equiv 6 \mod{7}\\
5(5) &\equiv 4 \mod{7}\\
5(6) &\equiv 2 \mod{7}\\
\end{align*}
Therefore, $x \equiv 2 \mod{7}$ gives the complete set of solutions. \qed
\vskip1em
\noindent \textbf{Solution 2:} This is equivalent to solving the LDE
\[
5x + 7y = 3
\]
A solution is given by $(x,y) = (2,-1)$. By LDET2, $x = 2 + 7n$ and $y = -1 + 5n$ for all $n$ gives the complete set of solutions. Hence $x \equiv 2 \mod{7}$ gives the complete solutions. \qed
\vskip1em
\noindent \textbf{Solution 3:} $5x \equiv 3 \mod{7} \Leftrightarrow x \equiv 2 \mod{7}$. We see this by multiplying by $5$ to go in reverse and multiplying by $3$ to go from the left to the right. Something like:
\begin{align*}
5x &\equiv 3 \mod{7}\\
(3)5x &\equiv (3)3 \mod{7}\\
15x &\equiv 9 \mod{7}\\
x &\equiv 2 \mod{7}
\end{align*}
and multiply by $3$ to go in reverse. 
\ic{Mention that this is related to something called finding an inverse for 5.}
\ex $2x \equiv 4 \mod{6}$.
\vskip1em
\soln Trying all $6$ possibilities yields,
\begin{align*}
2(0) &\equiv 0 \mod{6}\\
2(1) &\equiv 2 \mod{6}\\
2(2) &\equiv 4 \mod{6}\\
2(3) &\equiv 0 \mod{6}\\
2(4) &\equiv 2 \mod{6}\\
2(5) &\equiv 4 \mod{6}
\end{align*}
Hence, $x \equiv 2,5 \mod{6}$ give solutions. These solutions are captured by $x \equiv 2 \mod{3}$. (It is not a coincidence that $3 = 6/\gcd(2,4)$). \qed
\ic{Try to make this the 35 minute mark.}
Summarizing the above give the following theorem:
\vskip1em
\thm LCT1 (Linear Congruence Theorem 1). Let $a,c\in\mathbb{Z}$ and $m \in \mathbb{N}$ and $\gcd(a,m) = d$. Then $ax \equiv c \mod{m}$ has a solution if and only if $d \mid c$. Further, we have $d$ solutions modulo $m$ and $1$ solution modulo $m/d$. Moreover, if $x = x_{0}$ is a solution, then $x \equiv x_{0} \mod{m/d}$ forms the complete solution set or alternatively, $x = x_{0} + \tfrac{m}{d}n$ for all $n \in \mathbb{Z}$ or for another alternative way to write the solution:
\[
x \equiv x_{0}, x_{0} + \tfrac{m}{d}, x_{0} + 2\tfrac{m}{d} , ... , x_{0} + (d-1)\tfrac{m}{d} \mod{m}
\]
\pf Read p. 180. \qed
\ic{This is the 40-45 minute mark.}
\newpage
\hdc

Solve $9x \equiv 6 \mod{15}$. 
\vskip3em
\soln Notice that $9(4) = 36 \equiv 6 \mod{15}$. Hence, by LCT1, all solutions are given by $x \equiv 4 \mod{15/\gcd(9,15)}$, or $x \equiv 4 \mod{5}$. This is equivalent to $x \equiv 4, 9, 14 \mod{15}$.
\vskip1em
\textbf{Alternate Solution:} Equivalent to solving the LDE
\begin{align*}
9x + 15y &= 6\\
\implies 3x + 5y &= 2
\end{align*}
By LDET2, since $(x,y) = (-1,1)$ is a solution, all solutions are given by
\begin{align*}
x &= -1 + 5n\\
y &= 1 - 3n
\end{align*}
for all $n \in \mathbb{Z}$. 
Therefore, a solution is given by $x \equiv -1 \mod{5}$ or $x \equiv 4 \mod{5}$. Equivalently, $x \equiv 4,9,14 \mod{15}$. 

\ic{This is the 50 minute mark.}





