\documentclass{beamer} 



\useheadtemplate{% 
\vbox{% 
\vskip3pt% 
\colouredline{structure!75}{}%
{\color{structure!75}{}}% 
\insertvrule{0.4pt}{structure!50}% 
}} 

\usefoottemplate{% 
\vbox{% 
\colouredline{structure!75}% 
{\color{white}\textbf{ \insertshortinstitute}\hfill\textbf{\inserttitle}\hfill\insertpagenumber}% 
}} 

\usepackage{geometry}
\usepackage[latin1]{inputenc}
\usepackage[ngerman]{babel}
\usepackage{amsmath}
\usepackage{etex}
\usepackage{tikz}
\usetikzlibrary{arrows,backgrounds,snakes}
\usepackage[all]{xy}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage[all]{xy}
\usepackage{geometry}
\usepackage{ulem}
\usepackage{graphicx}
\usepackage{multirow}


\beamerboxesdeclarecolorscheme{alert}{structure!75}{blue!15!averagebackgroundcolor}
\beamerboxesdeclarecolorscheme{alert2}{structure!75}{blue!5!averagebackgroundcolor}
\beamerboxesdeclarecolorscheme{alert3}{}{blue!15!averagebackgroundcolor}



\begin{document} 

\frame[plain]{
\begin{center}
{\color{blue}\huge \bf Chinese Remainder Theorem \\ \medskip
explained with rotations}


\def\triangle{6cm}
\def\square{8cm}
\def\pentagon{10cm}
\def\octagon{3cm}
\def\trianglehour{1.3cm}
\def\squarehour{3cm}
\begin{figure}[!hbtp]

\begin{center}
\begin{tikzpicture}[scale=0.4]
\draw[color=violet!50] (0,0) circle (\squarehour);
\foreach \x in {1,2,...,4}{\node[circle,draw=violet!80, line width=0.5mm, inner sep=0pt,minimum size=12pt, fill=yellow!0] (1) at (90*\x :\squarehour) {}; \shade[shading=radial, inner color=violet!15, outer color=violet!85] (-90 :\squarehour) circle (0.65);};

\draw[color=violet!50] (0,0) circle (\trianglehour);
\foreach \x in {1,2,3} {\node[circle,draw=violet!80, line width=0.5mm, inner sep=0pt,minimum size=12pt, fill=yellow!0] (1) at (120*\x-30 :\trianglehour) {}; \shade[shading=radial, inner color=violet!15, outer color=violet!85] (-30 :\trianglehour) circle (0.65);};

\end{tikzpicture}
\end{center}
\end{figure}
\bigskip
\bigskip

{\bf Reference:} Antonella Perucca, \textit{The Chinese Remainder Clock},\\ The College Mathematics Journal, 2017, Vol. 48, No. 2, pp. 82-89.
\end{center}
}

\frame{
{\bf \Large \color{blue} One step-wise rotation}

Consider a circle with one marked point on it.

\begin{itemize}
\item Fix some positive integer $m$. 
At every time unit, let the point move $\frac{1}{m}$-th of the circle clockwise. 
\item This phenomenon is periodic, the fundamental period is $m$. 
\item We identify the positions with the integers from $0$ to $m-1$. For convenience, we set the initial position and $0$ at the top.
\end{itemize}
\bigskip

{\bf Example:} $m=3$, the position at time $0$

\def\trianglehour{1cm}

\begin{figure}[!hbtp]
\begin{tikzpicture}[scale=0.6]
\draw[color=green!50] (0,0) circle (\trianglehour);
\foreach \x in {1,2,3} {\node[circle,draw=green!80, line width=0.5mm, inner sep=0pt,minimum size=12pt, fill=yellow!0] (1) at (120*\x-30 :\trianglehour) {}; \shade[shading=radial, inner color=green!15, outer color=green!85] (90 :\trianglehour) circle (0.4);};
\end{tikzpicture}
\qquad\quad
%
\begin{tikzpicture}[scale=0.6]
\draw[color=green!50] (0,0) circle (\trianglehour);
\foreach \x in {1,2,3} {\node[circle,draw=green!80, line width=0.5mm, inner sep=0pt,minimum size=18pt, fill=yellow!0] (1) at (120*\x-30 :\trianglehour) {};};
\foreach \x in {0,1,2} {  \node[scale=0.5, scale=2] at (-120*\x+90 :\trianglehour) {\Large \x};};
\end{tikzpicture}
\end{figure}
}


\frame{
{\bf \Large \color{blue} Two simultaneous rotations}

Consider two simultaneous rotations with $m_1$ and $m_2$ steps.

\begin{itemize}
\item There are $m_1\cdot m_2$ configurations for the pair of points.
\end{itemize}
\bigskip

{\bf Example:} $m_1=3$ and $m_2=4$, the configuration at time $1$

\def\trianglehour{1cm}
\def\squarehour{2.4cm}


\begin{figure}[!hbtp]
\begin{tikzpicture}[scale=0.6]
\draw[color=green!50] (0,0) circle (\trianglehour);
\foreach \x in {1,2,3} {\node[circle,draw=green!80, line width=0.5mm, inner sep=0pt,minimum size=12pt, fill=yellow!0] (1) at (120*\x-30 :\trianglehour) {}; \shade[shading=radial, inner color=green!15, outer color=green!85] (-30 :\trianglehour) circle (0.4);};
\draw[color=blue!50] (0,0) circle (\squarehour); \foreach \x in {1,2,3,4}{\node[circle,draw=blue!80, line width=0.5mm, inner sep=0pt,minimum size=12pt, fill=yellow!0] (1) at (90*\x :\squarehour) {}; \shade[shading=radial, inner color=blue!15, outer color=blue!85] (0 :\squarehour) circle (0.4);};
\end{tikzpicture}
\qquad\quad
%
\begin{tikzpicture}[scale=0.6]
\draw[color=green!50] (0,0) circle (\trianglehour);
\foreach \x in {1,2,3} {\node[circle,draw=green!80, line width=0.5mm, inner sep=0pt,minimum size=18pt, fill=yellow!0] (1) at (120*\x-30 :\trianglehour) {};};
\foreach \x in {0,1,2} {  \node[scale=0.5, scale=2] at (-120*\x+90 :\trianglehour) {\Large \x};};
    
\draw[color=blue!50] (0,0) circle (\squarehour); \foreach \x in {1,2,3,4}{\node[circle,draw=blue!80, line width=0.5mm, inner sep=0pt,minimum size=18pt, fill=yellow!0] (1) at (90*\x :\squarehour) {};};
\foreach \x in {0,1,2,3} {  \node[scale=0.5, scale=2] at (-90*\x+90 :\squarehour) {\Large \x};}
\end{tikzpicture}
\end{figure}


}

\frame{
{\bf \Large \color{blue}Impossible configurations}

Consider two simultaneous rotations with $m_1$ and $m_2$ steps.

\begin{itemize}
\item In general, not all of configurations occur because the rotations are simultaneous (this is evident if $m_1 = m_2$).
\end{itemize}

{\bf Example:} $m_1=4$ and $m_2=6$, the configuration at time $7$ and an impossible configuration 

\def\square{1cm}
\def\hexagon{1.8cm}

\begin{figure}[!hbtp]
\begin{tikzpicture}[scale=0.8]
\draw[color=brown!50] (0,0) circle (\hexagon);  \foreach \x in {1,2,...,6} {\node[circle,draw=brown!80, line width=0.5mm, inner sep=0pt,minimum size=12pt, fill=yellow!0] (1) at  (60*\x+30:\hexagon)  {}; \shade[shading=radial, inner color=brown!15, outer color=brown!85] (30 :\hexagon) circle (0.3);};
\draw[color=blue!50] (0,0) circle (\square); \foreach \x in {1,2,3,4}{\node[circle,draw=blue!80, line width=0.5mm, inner sep=0pt,minimum size=12pt, fill=yellow!0] (1) at (90*\x :\square) {}; \shade[shading=radial, inner color=blue!15, outer color=blue!85] (180 :\square) circle (0.3);};
\end{tikzpicture}
\qquad\qquad
\begin{tikzpicture}[scale=0.8]
\draw[color=brown!50] (0,0) circle (\hexagon);  \foreach \x in {1,2,...,6} {\node[circle,draw=brown!80, line width=0.5mm, inner sep=0pt,minimum size=12pt, fill=yellow!0] (1) at  (60*\x+30:\hexagon)  {}; \shade[shading=radial, inner color=brown!15, outer color=brown!85] (-30 :\hexagon) circle (0.3);};
\draw[color=blue!50] (0,0) circle (\square); \foreach \x in {1,2,3,4}{\node[circle,draw=blue!80, line width=0.5mm, inner sep=0pt,minimum size=12pt, fill=yellow!0] (1) at (90*\x :\square) {}; \shade[shading=radial, inner color=blue!15, outer color=blue!85] (0 :\square) circle (0.3);};
\end{tikzpicture}
\end{figure}



}


\frame{
{\bf \Large \color{blue} Fundamental period for two rotations}


\begin{itemize}

\item {\bf  \color{blue} The fundamental period is the least common multiple of the single periods.}\\
Indeed, the fundamental period is the smallest positive time at which both points are back to the initial position, namely the least common multiple of $m_1$ and $m_2$.

\item Each configuration occurs at most once in every fundamental period (because getting the same configuration implies that both points did full turns).
\end{itemize}

We deduce:

\begin{itemize}
\item {\bf \color{blue} The fundamental period is the number of occurring configurations.}
\medskip

\item  Special case $m_1$ and $m_2$ coprime:\\ The fundamental period is $m_1\cdot m_2$, every configuration occurs.

\end{itemize}
}

\frame{
{\bf \Large \color{blue} Generalisation to several rotations}

Consider simultaneous rotations with $m_1, m_2\ldots, m_n$ steps.


\begin{itemize}

\item {\bf  \color{blue} The fundamental period is the least common multiple of the single periods.} \\
Namely, the least common multiple of $m_1, m_2\ldots, m_n$.
\medskip

\item Each configuration occurs at most once in every fundamental period.
\medskip

\item {\bf \color{blue} The fundamental period is the number of occurring configurations.}
\medskip

\item  Special case $m_1, m_2\ldots, m_n$ pairwise coprime:\\ The fundamental period is the product $m_1\cdots m_n$, every configuration occurs.

\end{itemize}
}

\frame{
{\bf \Large \color{blue} CRT for rotations}

We have thus proven:
\bigskip


\begin{beamerboxesrounded}[scheme=alert,shadow=true]{Chinese Remainder Theorem for rotations}
Let $m_1,\cdots, m_n$ be pairwise coprime positive integers. For each integer $m$ in this set, consider a circle with one marked point on it, which at every time unit rotates of $\frac{1}{m}$-th of the circle clockwise. The fundamental period for this phenomenon is $m_1\cdots m_n$, and every configuration for the $n$-tuple of marked points occurs exactly once in the fundamental period.
\end{beamerboxesrounded}
\bigskip

{\bf Remark:} Even if the integer parameters are not coprime, the configuration of the marked points determines the time inside a fundamental period because it occurs at most once.

}

\frame{
{\bf \Large \color{blue} CRT for cyclic periodic phenomena}

Consider a cyclic periodic phenomenon, where finitely many distinct situations repeat
cyclically. This can be seen as a rotation with as many steps as the fundamental period, so we have proven:
\bigskip

\begin{beamerboxesrounded}[scheme=alert,shadow=true]{Chinese Remainder Theorem for cyclic periodic phenomena}
If $m_1,\cdots, m_n$ are pairwise coprime positive integers, then a cyclic periodic phenomenon with fundamental period $m_1\cdots m_n$ amounts to the collection of simultaneous cyclic periodic phenomena whose fundamental periods are $m_1$ to $m_n$.
\end{beamerboxesrounded}
\bigskip

{\bf Corollary:} A cyclic periodic phenomenon with fundamental period $m$ can be described by cyclic periodic phenomena whose fundamental periods are the prime powers appearing in the factorization of $m$.
}

\frame{
{\bf \Large \color{blue} CRT for lists of remainders}


\begin{beamerboxesrounded}[scheme=alert,shadow=true]{Chinese Remainder Theorem for lists of remainders}
Let $m_1,\cdots, m_n$ be pairwise coprime positive integers. For every integer consider the n-tuple of its remainders after division by $m_1$ to $m_n$. We then have:
\begin{itemize}
\item Two integers produce the same n-tuple if and only if they leave the same remainder after division by the product $m_1\cdots m_n$.
\item All $n$-tuples consisting of remainders after division by $m_1$ to $m_n$ are produced.
\end{itemize}

\end{beamerboxesrounded}
\bigskip

{\bf Proof:} The result can be deduced from the CRT for rotations. \\ A list of remainders can be  identified (in an obvious way) with a configuration of marked points.\hfill $\square$
}


\frame{
{\bf \Large \color{blue} The usual CRT}


\begin{beamerboxesrounded}[scheme=alert,shadow=true]{Chinese Remainder Theorem}
Let $m_1,\cdots, m_n$ be pairwise coprime positive integers. An integer in the range from $0$ to $m_1\cdots m_n-1$ is uniquely determined by the $n$-tuple of its remainders after division by $m_1$ to $m_n$.
\end{beamerboxesrounded}
\bigskip

{\bf Proof:} This is a reformulation of the previous result.\hfill $\square$



}


\frame{
{\bf \Large \color{blue} Generalisation of the usual CRT}

\bigskip

\begin{beamerboxesrounded}[scheme=alert,shadow=true]{Generalized Chinese Remainder Theorem}
Let $m_1,\cdots, m_n$ be positive integers. An integer in the range from $0$ to $\mathrm{lcm}(m_1,\ldots m_n)-1$ is uniquely determined by the $n$-tuple of its remainders after division by $m_1$ to $m_n$.
\end{beamerboxesrounded}
\bigskip

{\bf Proof:} The result can be deduced from the corresponding result about simultaneous step-wise rotations.
\hfill $\square$\bigskip

Remark that an impossible $n$-tuple of remainders corresponds to an impossible configuration for the $n$-tuple of marked points.

}


\frame{

\begin{center}
{\bf \Huge \color{blue} Thank you\\ for your attention!}

\end{center}


}

\end{document}