\newlec

Leading Question: Is $98654320480$ divisible by $120$? 

\ic{Note that $120 = 5!$}

\textbf{Divisibility Rules}

\vskip1em
A positive integer $n$ is divisible by 
\begin{enumerate}[A)]
\item $2^{k}$ if and only if the last $k$ digits are divisible by $2^{k}$ where $k \in \mathbb{N}$.
\item 3 (or 9) if and only if the sum of the digits is divisible by 3 (or 9).
\item $5^{k}$ if and only if the last $k$ digits are divisible by $5^{k}$ where $k \in \mathbb{N}$.
\item $7$ (or 11 or 13) if and only if the alternating sum of triples of digits is divisible by $7$ (or 11 or 13).
\vskip1em
\ex $n = 123456333$. Look at $333- 456+123 = 0$ Since $7 \mid 0$ (and 11 and 13), we see that $7 \mid n$ (and 11 and 13).
\end{enumerate}
We prove that 9 divides a number $n$ if and only if the sum of the digits is divisible by 9.
\vskip1em
\pf Let $n \in \mathbb{N}$. Write 
$$
n = d_{0} + 10d_{1} + 10^{2}d_{2} + ... + 10^{k} d_{k}
$$
where $d_{i} \in \{0,1,2,..., 9\}$. (For example, $213 = 3 + 10(1) + 100(2)$). Thus,
\begin{align*}
9 \mid n &\Leftrightarrow n \equiv 0 \mod{9}\\
&\Leftrightarrow 0 \equiv d_{0} + 10d_{1} + ... + 10^{k}d_{k} \mod{9}\\
&\Leftrightarrow 0 \equiv  d_{0} + d_{1} + ... + d_{k}\mod{9} &&\text{By (PC)}\\
&\Leftrightarrow 9 \mid (d_{0} + d_{1} + ... + d_{k})
\end{align*}
Hence $9 \mid n$ if and only if $9$ divides the sum of the digits of $n$. \qed
\ic{Note this is the first time I used an iff bidirectional proof. If this is your first time too you should make a note. This is the 10-15 minute mark. Note that if you're running low on time you needn't write out all the divisibility rules (or even mention them!)}
Let's look at some examples of division of congruences. Can I divide integers with congruences? 
\begin{enumerate}
\item $3 \equiv 24 \mod{7}$
\item $1 \equiv 8 \mod{7}$
\item $3 \equiv 27 \mod{6}$
\item $1 \not \equiv 9 \mod{6}$
\end{enumerate}
The above examples suggests that if you're dividing by a number that is coprime to the modulus, then you can divide. This is true in general.
\vskip1em
\prop (Congruences and Division (CD)). Let $a,b,c \in \mathbb{Z}$ and let $n \in \mathbb{N}$. If $ac \equiv bc \mod{n}$ and $\gcd(c,n) = 1$, then $a \equiv b \mod{n}$.
\vskip1em
\pf By assumption, $n \mid (ac - bc)$ so $n \mid c(a-b)$. Since $\gcd(c,n) = 1$, by Coprimeness and Divisibility, $n \mid (a-b)$. Hence $a \equiv b \mod{n}$.
\ic{This is the 20-25 minute mark. introduce the next proposition as something they know but helps organize thoughts.}
\prop (Congruent iff Same Remainder - CISR) Let $a,b\in\mathbb{Z}$. Then $a \equiv b \mod{n}$ if and only if $a$ and $b$ have the same remainder after division by $n$.
\ic{Delay the proof until after they get a chance to use it.}
\newpage
What is the remainder when $77^{100}(999) - 6^{83}$ is divided by $4$?
\vskip3em
\soln Notice that 
\begin{align*}
6 = 4(1) + 2 \quad\quad 77 = 19(4) + 1 \quad\quad  999 = 249(4) + 3
\end{align*}
Hence, by Congruent if and only if Same Remainder, we have $77 \equiv 1 \mod{4}$ and $999 \equiv 3 \mod{4}$. Thus, by Properties of Congruences, 
\begin{align*}
77^{100}(999) - 6^{83} &\equiv (1)^{100}(3) - 2^{83} \mod{4}\\
&\equiv 3 - 2^{2}\cdot 2^{81} \mod{4}\\
&\equiv 3- 4\cdot2^{81} \mod{4} \\
&\equiv 3-0(2^{81}) \mod{4}\\
&\equiv 3 \mod{4}
\end{align*}
Once again by Congruent If and only If Same Remainder, $3$ is the remainder when $77^{100}(999) - 6^{83}$ is divided by $4$. \qed
\newpage
Restating,
\vskip1em
\prop (Congruent iff Same Remainder - CISR) Let $a,b\in\mathbb{Z}$. Then $a \equiv b \mod{n}$ if and only if $a$ and $b$ have the same remainder after division by $n$.
\vskip1em
\pf By the Division Algorithm, write $a = nq_{a} + r_{a}$ and $b = nq_{b} + r_{b}$ where $0 \leq r_{a},r_{b} < n$. Subtracting gives
\[
a-b = n(q_{a} - q_{b}) + r_{a}-r_{b}
\]
To prove $\Rightarrow$, first assume that $a \equiv b \mod{n}$, that is $n \mid a-b$. Since $n \mid n(q_{a}-q_{b})$, we have by Divisibility of Integer Combinations that
$n \mid (a-b) + n(q_{a}-q_{b})(-1) $ and thus, $n \mid r_{a}-r_{b}$.
By our restriction on the remainders, we see that the difference is bounded by
\[
-n+1 \leq r_{a}-r_{b} \leq n-1
\]
However, only $0$ is divisible by $n$ in this range! Since $n \mid(r_{a}-r_{b})$, we must have that $r_{a} - r_{b} = 0$. Hence $r_{a} = r_{b}$. 
\vskip1em
$\Leftarrow$ Assume that $r_{a} = r_{b}$. Since
\[
a-b = n(q_{a} - q_{b}) + r_{a}-r_{b} = n(q_{a}-q_{b})
\]
we see that $n \mid (a-b)$ and hence $a \equiv b \mod{n}$. \qed
\ic{This is likely the 50 minute mark. If it isn't get students to work or think about the following problem which you'll take up in the next class.}
\qn What is the last digit of $5^{32}3^{10} + 9^{22}$?



