\newlec

\hdc
Find the remainder when $7^{92}$ is divided by $11$. 
\vskip3em
\soln Recall (F$\ell$T): If $p \nmid a$, then $a^{p-1} \equiv 1 \mod{p}$ where $p$ is a prime.
\vskip1em
By F$\ell$T, 
\begin{align*}
7^{10} &\equiv 1 \mod{11}\\
7^{90} &\equiv 1 \mod{11} & \text{Raise both sides to the power of 9}\\
7^{92} &\equiv 7^{2} \equiv 49 \equiv 5 \mod{11}
\end{align*}
Alternatively,
\begin{align*}
7^{92} &\equiv 7^{9(10)+2} \mod{11}\\
&\equiv (7^{10})^{9}7^{2} \mod{11}\\
&\equiv 1^{9} \cdot 7^{2} \mod{11} &&\text{ By F$\ell$T since $11 \nmid 7$}\\
&\equiv 49 \mod{11}\\
&\equiv 5 \mod{11}
\end{align*}
completing the question. \qed
\ic{This is the 10 minute mark}
\newpage
\cor If $p$ is a prime and $a \in \mathbb{Z}$, then $a^{p} \equiv a \mod{p}$. 
\vskip1em
\pf If $p \mid a$, then $a \equiv 0 \mod{p}$. This implies that $a^{p} \equiv 0 \equiv a \mod{p}$. 
\vskip1em
If $p \nmid a$, then by F$\ell$T, $a^{p-1} \equiv 1 \mod{p}$ and hence $a^{p} \equiv a \mod{p}$ completing the proof. \qed
\vskip1em
\cor If $p$ is a prime number and $[a] \neq [0]$ in $\mathbb{Z}_{p}$, then there exists a $[b] \in \mathbb{Z}_{p}$ such that $[a][b] = [1]$. 
\vskip1em
\pf Since $[a] \neq [0]$, we see that $p \nmid a$. Hence by F$\ell$T, $a^{p-1} \equiv 1 \mod{p}$ and thus $a\cdot a^{p-2}\equiv1 \mod{p}$. This is sensible since $p-2 \geq 0$. Thus, take $[b] = [a^{p-2}]$. \qed
\ic{Students should be able to do the next one - give them a shot at it on their own first! There's a handout one that depends on this so it might be good to get them thinking.}
\cor If $r = s + kp$, then $a^{r} \equiv a^{s+k} \mod{p}$ where $p$ is a prime and $a \in \mathbb{Z}$ and $r,s,k \in \mathbb{N}$.
\vskip1em
\ic{It should be noted that here we want $r,s,k$ to be at least nonnegative. We haven't really talked about what it means to take $a^{k}$ when $k < 0$ except for $k=-1$. It's not hard but in this corollary, the important fact is that $a$ might not be invertible so things like $a^{-3}$ don't make sense necessarily.}
\vskip1em
\pf We have
\begin{align*}
a^{r} &\equiv a^{s + kp} \mod{p}\\
&\equiv a^{s}(a^{p})^{k} \mod{p}\\
&\equiv a^{s}(a)^{k} \mod{p} && \text{By corollary to F$\ell$T}\\
&\equiv a^{s+k} \mod{p}
\end{align*}
\ic{This is the 20 minute mark.}

\newpage
\hdc
Let $p$ be a prime. Prove that if $p \nmid a$ and $r \equiv s \mod{(p-1)}$, then $a^{r} \equiv a^{s} \mod{p}$ for any $r,s \in \mathbb{Z}$.
\vskip3em
\soln Since $r \equiv s \mod{(p-1)}$, we have that $(p-1) \mid (r-s)$. Thus, there exists a $k \in \mathbb{Z}$ such that $(p-1)k = r-s$. Hence $r = s + (p-1)k$. Thus,
\begin{align*}
a^{r} &\equiv a^{s + (p-1)k} \mod{p}\\
&\equiv a^{s}(a^{p-1})^{k} \mod{p}\\
&\equiv a^{s}(1)^{k} \mod{p} &&\text{ By F$\ell$T since $p \nmid a$}\\
&\equiv a^{s} \mod{p}.
\end{align*}
This completes the proof. \qed

\ic{This is the 30 minute mark}

\newpage

\textbf{Chinese Remainder Theorem (CRT)}
\vskip1em
Solve 
\begin{align*}
x &\equiv 2 \mod{7}\\
x &\equiv 7 \mod{11}
\end{align*}
\ic{Note to students this is the first time they are seeing two congruences with different moduli.}
Using the first condition, write $x = 2 + 7k$ for some $k \in \mathbb{Z}$. Plugging into the second condition gives 
\begin{align*}
2 + 7k &\equiv 7 \mod{11}\\
7k &\equiv 5 \mod{11}
\end{align*}
Now there are a few ways to proceed. One could guess and check the inverse of $7$. With this approach, we see that multiplying both sides by $3$ gives
\begin{align*}
3\cdot 7k &\equiv 15 \mod{11}\\
21 k &\equiv 4 \mod{11}\\
-k &\equiv 4 \mod{11}\\
k &\equiv -4 \mod{11}\\
k &\equiv 7 \mod{11}
\end{align*}
Therefore, $k = 7 + 11\ell$ for some $\ell \in \mathbb{Z}$. Alternatively, one can use the LDE approach on $7k + 11y = 5$ and use the Extended Euclidean Algorithm:
\begin{table}[ht!]
%\caption{default}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
k & y & r & q\\
\hline 
0 & 1 & 11 & 0 \\
1 & 0 & 7 & 0 \\
-1 & 1 & 4 & 1\\
2 & -1 & 3 & 1\\
-3 & 2 & 1 & 1\\
& & 0 & 3\\
\hline
\end{tabular}
\end{center}
%\label{default}
\end{table}%
\vskip1em
Hence $7(-3) + 11(2) = 1$ and thus $7(-15) + 11(10) = 5$. So by LDET2, we have that $k = -15 + 11n$ for all $n \in \mathbb{Z}$. Thus $k \equiv -15 \equiv 7 \mod{11}$ and as above $k = 7 + 11\ell$ for some $\ell \in \mathbb{Z}$.
\ic{Note here that to find all solution we need to use for all $n \in \mathbb{Z}$. Because out specific $k$ is fixed however, we us for some at the end. What's happened here is that we've overloaded the use of $k$ - once in the question but once in the LDE question process. This isn't a big deal and probably isn't worth mentioning unless a student asks.}
Thus, since $x = 2 + 7k$ and $k = 7 + 11\ell$, we have
\begin{align*}
x &= 2 + 7k\\
&= 2 + 7(7+11\ell)\\
&= 51 + 77\ell
\end{align*}
Therefore, $x \equiv 51 \mod{77}$ is the solution. \qed
\ic{This might take you to the 50 minute mark. Otherwise state the slide on the next lecture.}






