\newlec

\ic{First part is to recall the definition of congruence. This is extremely important. Get students to do this on their own}

\defn Let $a, b\in\mathbb{Z}$ and $n \in \mathbb{N}$. Then $a$ is congruent to $b$ modulo $n$ if and only if $n \mid (a-b)$ and we write $a \equiv b \mod{n}$. This is equivalent to saying there exists an integer $k$ such that $a-b = kn$ or $a = b + kn$.
\ic{This is the 5 minute mark}

\newpage
\hdc
\ic{Write on the board and get students to prove. These are follow your nose proofs}
\textbf{Congruence is an Equivalence Relation (CER)}
\vskip0.1em
Let $n \in \mathbb{N}$. Let $a,b,c \in \mathbb{Z}$. Then
\begin{enumerate}
\item (Reflexivity) $a \equiv a \pmod{n}$.
\item (Symmetry) $a \equiv b \pmod{n} \Rightarrow b \equiv a \pmod{n}$.
\item (Transitivity) $a \equiv b \pmod{n}$ and $b \equiv c \pmod{n} \Rightarrow a \equiv c \pmod{n}$.
\end{enumerate}

\vskip3em
\pf
\begin{enumerate}
\item Since $n \mid 0 = (a-a)$, we have that $a \equiv a \pmod{n}$.
\item Since $n \mid (a-b)$, there exists an integer $k$ such that $nk=(a-b)$. This implies that $n(-k)=b-a$ and hence $n \mid (b-a)$ giving $b \equiv a \pmod{n}$.
\item Since $n \mid (a-b)$ and $n \mid (b-c)$, by Divisibility of Integer Combinations, $n \mid ((a-b)+(b-c))$. Thus $n \mid (a-c)$ and hence $a \equiv c \pmod{n}$
\end{enumerate}

\ic{This is the 20 minute mark}
\newpage
\ex Without a calculator, determine if $167 \equiv 2015 \mod{4}$ is true.
\vskip1em
\soln Since $2015 \equiv 3 \mod{4}$ (valid as $4 \mid 2012 = 2015-3$) and $167 \equiv 3 \mod{4}$ (valid as $4 \mid 164 = 167-3$), we see by symmetry that $3 \equiv 2015 \mod{4}$ and hence by transitivity that $167 \equiv 2015 \mod{4}$.
\vskip1em
\noindent \textbf{Alternate Solution:} Does $4 \mid (2015-167) = 1848$?

\ic{This is the 25 minute mark}
\newpage
\hdc
\ic{Write on board and get students to prove on their own}
\textbf{Properties of Congruence (PC)}
Let $a,a',b,b' \in \mathbb{Z}$. If $a \equiv a' \pmod{m}$ and $b \equiv b' \pmod{m}$, then
\begin{enumerate}
\item $a+b \equiv a'+b' \pmod{m}$
\item $a-b \equiv a'-b' \pmod{m}$
\item $ab \equiv a'b' \pmod{m}$
\end{enumerate}

\vskip3em
\pf
\begin{enumerate}
\item Since $m \mid (a-a')$ and $n \mid (b-b')$, we have by Divisibility of Integer Combinations $m \mid (a-a'+(b-b'))$. Hence $m \mid ((a+b)-(a'+b'))$ and so  $a+b \equiv a'+b' \pmod{m}$.
\item Since $m \mid (a-a')$ and $n \mid (b-b')$, we have by Divisibility of Integer Combinations $m \mid (a-a'-(b-b'))$. Hence $m \mid ((a-b)-(a'-b'))$ and so  $a-b \equiv a'-b' \pmod{m}$.
\item Since $m \mid (a-a')$ and $n \mid (b-b')$, we have by Divisibility of Integer Combinations $m \mid ((a-a')b+(b-b')a')$. Hence $m \mid ab-a'b'$ and so  $ab \equiv a'b' \pmod{m}$.
\end{enumerate}

\ic{This is the 40 minute mark}

\newpage
\textbf{Corollary} If $a \equiv b \pmod{m} $ then $a^{k} \equiv b^{k} \pmod{m}$ for $k \in \mathbb{N}$.
\vskip0.1em
\textbf{Example:} Since $2 \equiv 6 \mod{4}$, we have that \vskip0.1em $2^{2} \equiv 6^{2} \mod{4}$, that is, $4 \equiv 36 \mod{4}$.



\ex Is $5^{9} + 62^{2000} - 14$ divisible by $7$?
\vskip1em
\soln Reduce modulo $7$. By Properties of Congruence, we have
\begin{align*}
5^{9} + 62^{2000} - 14 &\equiv (-2)^{9} + (-1)^{2000} - 0 \mod{7}\\
&\equiv -2^{9} + 1\mod{7}\\
&\equiv -(2^{3})^{3} + 1 \mod{7}\\
&\equiv -(8)^{3} + 1 \mod{7}\\
&\equiv -(1)^{3} + 1 \mod{7}\\
&\equiv 0 \mod{7}
\end{align*}
Therefore, the number is divisible by $7$. 
\ic{This is the 50 minute mark. Some things to note above: In computations, we often don't cite every single time a basic proposition is used like PC or CER or the major corollary above. Be sure though while explaining to mention the use of the corollary above.}