\newlec
\hdc

\thm [Chinese Remainder Theorem (CRT)
If \newline$\gcd(m_1,m_2) = 1$, then for any choice of integers $a_1$ and $a_2$, there exists a solution to the simultaneous congruences
\begin{eqnarray*}
n & \equiv & a_1 \pmod{m_1} \\
n & \equiv & a_2 \pmod{m_2}
\end{eqnarray*}
Moreover, if $n = n_0$ is one integer solution, then the complete solution is $n \equiv n_0 \pmod{m_1m_2}$.
\vskip1em
\thm (Generalized CRT (GCRT)) If $m_1, m_2, \ldots, m_k $ are integers and $\gcd(m_i, m_j) = 1$ whenever $i \neq j$, then for any choice of integers $a_1, a_2, \ldots, a_k$, there exists a solution to the simultaneous congruences
\begin{align*}
n & \equiv a_1 \pmod {m_1} \\
n & \equiv a_2 \pmod {m_2} \\
  & \vdots \\
n & \equiv a_k \pmod {m_k}
\end{align*}
Moreover, if $n = n_0$ is one integer solution, then the complete solution is
\[ n \equiv n_0 \pmod{m_1 m_2 \ldots m_k} \]

\vskip3em

\ic{This is the 5 minute mark. Remark that the statement of CRT is not nearly as useful as understanding the proof.}

\newpage

\ex Solve 
\begin{align*}
x &\equiv 5 \mod{6}\\
x &\equiv 2 \mod{7}\\
x &\equiv 3 \mod{11}
\end{align*}
From the first equation, $x = 5 + 6k$ for some $k \in \mathbb{Z}$. Plug this into the second equation gives
\begin{align*}
5 + 6k &\equiv 2 \mod{7}\\
6k &\equiv -3 \mod{7}\\
-k &\equiv -3 \mod{7}\\
k &\equiv 3 \mod{7}
\end{align*}
and hence $k = 3 + 7\ell$ for some $\ell \in \mathbb{Z}$. Therefore, $x = 5 + 6(3 + 7\ell) = 23 + 42\ell$. Therefore $x \equiv 23 \mod{42}$. Now, we need to satisfy
\begin{align*}
x &\equiv 23 \mod{42}\\
x &\equiv 3 \mod{11}
\end{align*}
\ic{This is done so that students can see the reduction pattern that emerges.}
Since $x = 23 + 42\ell$, plugging this into the final equation gives
\begin{align*}
23 + 42\ell &\equiv 3 \mod{11}\\
-2\ell &\equiv -20 \mod{11}\\
\ell &\equiv 10 \mod{11} &&\text{ By Congruences and Divisibility [CD] valid since $\gcd(-2,11) = 1$}
\end{align*}
Hence, $\ell = 10 + 11m$ for some $m \in \mathbb{Z}$. Combining gives
\[
x = 23 + 42\ell = 23 + 42(10 + 11m) = 443 + 462m
\]
Therefore, $x \equiv 442 \mod{462}$.
\ic{This is the 20 minute mark.}
\textbf{Some twists to Chinese Remainder Problems:}
\ex Solve 
\begin{align*}
3x &\equiv 2 \mod{5}\\
2x &\equiv 6\mod{7}
\end{align*}
\ic{The twist here is that the left hand sides are not just $x$ but they have a coefficient.}
\soln Treat each congruence separately and solve using Linear Congruence Theorem 1 (LCT1). By inspection $x =4$ solves the first congruence (could also use Linear Diophantine Equation techniques). Hence by LCT1, $x \equiv 4 \mod{5/\gcd(3,5)}$ or $x \equiv 4 \mod{5}$. Similarly, notice that $x=3$ is a solution to the second congruence. Hence by LCT1 again, $x \equiv 3 \mod{7/\gcd(2,7)}$. This is equivalent to $x \equiv 3 \mod{7}$. Thus, the above system is equivalent to solving
\begin{align*}
x &\equiv 4 \mod{5}\\
x &\equiv 3 \mod{7}
\end{align*}
which can be solved like a typical Chinese Remainder Theorem problem.
\ic{Don't do this in class - included only because I used to solve this this way.}
{\bf Alternate Solution:} Multiplying the first equation by $2$ and the second equation by $4$ gives
\begin{align*}
6x &\equiv 4 \mod{5}\\
8x &\equiv 24 \mod{7}.
\end{align*}
Simplifying gives
\begin{align*}
x &\equiv 4 \mod{5}\\
x &\equiv 3 \mod{7}
\end{align*}
Then proceed like a typical Chinese Remainder Theorem problem.
\vskip1em
\ex Solve 
\begin{align*}
x &\equiv 4 \mod{6}\\
x &\equiv 2 \mod{8}
\end{align*}
\ic{The twist here is that the moduli are not coprime. Turns out that the engine that proves the Chinese Remainder Theorem is exactly what one needs to do here. Sometimes however there are no solutions and usually there are solutions but at a moduli smaller than the product.}
\soln Using the first equation gives $x = 4 + 6k$ for some $k \in \mathbb{Z}$. Plug this into the second equation gives
\begin{align*}
4 + 6k &\equiv 2 \mod{8}\\
6k &\equiv -2 \mod{8}\\
6k &\equiv 6 \mod{8}
\end{align*}
Now, note that $k=1$ is definitely a solution. By LCT1, we have that 
\[
k \equiv 1 \mod{8/(\gcd(6,8))}
\]
gives all solution. Hence $k \equiv 1 \mod{4}$ and thus $k = 1 + 4\ell$ for some $\ell \in \mathbb{Z}$. Therefore,
\[
x = 4 + 6(1 + 4\ell) = 10 + 24\ell
\]
Therefore, $x \equiv 10 \mod{24}$ gives the complete set of solutions.
\ic{This is the 40 minute mark. Could even take your time and make this a full lecture if you wanted. We're reaching a catch up lecture if you have fallen behind.}
\ex Solve $x^{2} \equiv 34 \mod{99}$.
\vskip1em
This implies that $99 \mid (x^{2} - 34)$. Note that $9 \mid 99$. Therefore $9 \mid (x^{2} - 34)$ by transitivity, $x^{2} \equiv 34 \mod{9}$. Note further that $11 \mid 99$. Therefore, $11 \mid (x^{2} - 34)$ by transitivity. this implies that 
\begin{align*}
x^{2} &\equiv 34 \mod{11}\\
x^{2} &\equiv 1 \mod{11}\\
x^{2} &\equiv \pm 1 \mod{11} &&\text{ By trying all 11 possibilities}
\end{align*}
Similarly, $x^{2} \equiv 34 \equiv 7 \mod{9}$ and so $x \equiv \pm 4 \mod{9}$ (try all 9 possibilities).
\vskip1em
This gives four systems of equations:
\begin{align*}
x &\equiv 1 \mod{11} \quad & \quad x &\equiv 1 \mod{11}\\
x &\equiv 4 \mod{9} \quad  &\quad x &\equiv -4 \mod{9}
\end{align*}

\begin{align*}
x &\equiv -1 \mod{11} \quad & \quad x &\equiv -1 \mod{11}\\
x &\equiv 4 \mod{9} \quad  &\quad x &\equiv -4 \mod{9}
\end{align*}
To finish solving this, we can use the Chinese Remainder Theorem $4$ times to give the solutions
\[
x \equiv 23,32,67,76 \mod{99}
\]
This leads to the following theorem.
\vskip1em
\thm Splitting the Modulus (SM) Let $m$ and $n$ be coprime positive integers. Then, for any integers $x$ and $a$, we have
\begin{align*}
x &\equiv a \mod{m}\\
x &\equiv a \mod{n}
\end{align*}
simultaneously if and only if $x \equiv a \mod{mn}$.
\ic{This is the 50 minute mark. If not, start the proof.}






