\documentclass[10pt,a4paper,english]{amsart} \usepackage{geometry} \usepackage{tikz} \usepackage{url} \usepackage{amssymb,latexsym} \usepackage{amsfonts, amsmath, amsthm, amssymb, fancybox, graphicx, color, times, babel} \usepackage[bookmarksnumbered,colorlinks,bookmarks,citecolor=black,linkcolor=black,urlcolor=black,breaklinks,linktocpage]{hyperref} \DeclareMathOperator{\lcm}{lcm} \begin{document} \begin{center} {{\color{blue}\Large \bf THE CHINESE REMAINDER CLOCK TUTORIAL}}\\\medskip {John Perry and Antonella Perucca} \end{center} \tableofcontents \noindent{The overall goal of this tutorial is that you understand how a Chinese Remainder Clock works.} Along the way you learn something about division with remainder and the fascinating properties of the remainders. In particular, { you discover the famous Chinese Remainder Theorem.} \noindent Throughout this tutorial we work with the ``natural numbers'', which are the number $0,1,2,3\ldots$. You can think of them as numbers that appear ``naturally'' when you count. \section*{Division with Remainder}%%%%%% \noindent {One way to think of division is that you are dividing a set of objects into groups.} For instance, you can divide chocolates among children, but that makes us too hungry to do math, so instead we think about dividing balls among teams. \subsection*{The division equation}%%% If you divide 7 by 2 you have quotient 3 and remainder 1: $$7=3\times 2 +1\,.$$ \noindent In general you divide a natural number, \emph{the dividend} (7 in the example), by another natural number, \emph{the divisor} (2 in the example). The dividend is a multiple of the divisor (in the example, 3 times the divisor) plus some number, called \emph{the remainder} (in the example, 1). The multiple of the divisor that you consider (in the example, $3\times 2$) is the product of a number, called \emph{the quotient} (in the example, 3), and the divisor.\\ \noindent All the numbers involved fit into a nice equation: $$Dividend = Quotient \times Divisor + Remainder\,.$$ You can see this in our equation above: $7=3\times2+1$. \subsection*{About dividend and divisor}%%% When dividing, \emph{we divide the dividend by the divisor}. \begin{itemize} \item The dividend is a natural number (possibly zero). \item The divisor is a non-zero natural number. \end{itemize} \noindent We cannot divide by zero, it is forbidden!\\ \noindent For example, earlier we looked at \[ 7 = 3\times2 + 1\ .\] Imagine that you have 7 balls (the dividend), and you need to divide them among 2 teams (the divisor). You can give each team 3 balls (the quotient) and you have 1 ball left over (the remainder).\\ \noindent An important point to keep in mind is that \emph{the remainder must always be smaller than the divisor}; otherwise, you haven't divided as much as possible! In our example above, we could also give each team 2 balls, and that would leave 3 balls: \[ 7 = 2\times2 + 3\ .\] But there are still 3 balls undistributed (the remainder) and 2 teams (the divisor), so we haven't distributed as many balls as we could. If we do distribute as many as possible, we end up with \[ 7 = 3\times2 + 1\ .\] After all, you cannot divide the one remaining ball among two teams without doing serious damage to the ball!\\ \noindent Here is another example. If we divide 0 by 5 we have quotient 0 and remainder 0: $$0=5\times 0 +0$$ After all, if you distribute 0 balls to 5 teams, then each team receives 0 balls (the quotient) and 0 balls are left over (the remainder). Notice that the remainder, 0, is smaller than the divisor, 5. So ``division \textit{of} zero'' is 0. \noindent However, we cannot divide 5 by 0. We cannot even divide 0 by 0! After all, if you have 5 balls and distribute them to 0 teams, then you always have 5 balls left over, regardless of how many balls you give to each team. You can give 1 ball to each team, or 2 balls to each team, or 3 balls to each team\ldots You can even give 100 balls to each team, and you'd have 5 balls left over! The remainder is not smaller than the divisor, so we leave ``division \textit{by} zero'' undefined and say ``you cannot do it!''. \subsection*{About quotient and remainder}%%% Let's think about quotient and remainder a little more.\\ \noindent \emph{The remainder is smaller than the divisor.} \noindent For example, if we divide 15 by 5, we could write $$15=1\times 5 +10\ ,$$ but $10$ is no valid remainder because it is not smaller than $5$. This won't surprise you, however, because we've already discussed it.\\ %Of course, this comes as no surprise, because we discussed it already. We promised we wouldn't discuss chocolate, but this is a good place to make an exception: if you have 15 chocolates, and distribute 1 chocolate to each of 5 children, you will have 10 chocolates left over. That won't do, because the children will want more, so you have to keep distributing until the number of chocolates is fewer than the number of children. (Of course, you could just not buy chocolates for the children, which may be physically healthier for them, but then your children will see other children with chocolate, and will be psychologically damaged for the remainder of their lives. --- Well, perhaps not, but they'll certainly act as if it's an irreparable harm.)\\ \noindent \emph{The quotient is a natural number, possibly zero.} For example, if we divide 5 by 7 we have quotient 0 and remainder 5: $$5=0\times 7 +5\ .$$ This is because we cannot divide 5 balls evenly among 7 teams. Notice that the remainder, 5, is smaller than the divisor, 7.\\ \noindent\emph{The remainder is a natural number, possibly zero.} \noindent For example, if we divide 15 by 5 we have quotient 3 and remainder 0: $$15=3\times 5 +0\ .$$ This is because we can divide 15 balls evenly among 5 teams, and no balls are left over. Again, the remainder, 0, is smaller than the divisor, 5.\\ \noindent We can also divide by $1$, and the remainder is always $0$. For example, if we divide $7$ by $1$ then we have quotient $7$ and remainder 0: $$7=7\times 1 +0\ .$$ After all, ``dividing by 1'' really means giving everything to one person, and then there's nothing left over. %(This is another good place for an exception to the rule on chocolates. If you distribute all the chocolates to one child, you will have none left over, and in a short time the child will also have none left over. Of course, if the child has siblings, you will have something left over: a lot of complaints!)\\ \subsection*{Summary}%%% \noindent In division with remainder for natural numbers we start with: \begin{itemize} \item One natural number, the dividend. \item One natural number, the divisor (which cannot be zero!). \end{itemize} We divide the dividend by the divisor, obtaining: \begin{itemize} \item One natural number, the quotient. \item One natural number, the remainder (which is strictly smaller than the divisor!). \end{itemize} These numbers fit into the equation $$Dividend = Quotient \times Divisor + Remainder\,.$$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{Remainders}%%%%%% \subsection*{Divisibility}%%% Related to division is the idea of divisibility. \begin{itemize} \item If the remainder is zero, then the dividend is a multiple of the divisor. \item If the dividend is a multiple of the divisor, then the remainder is zero. \end{itemize} \noindent For example, 8 divided by 4 leaves remainder 0 is related to the fact that 8 is a multiple of 4.\\ \noindent Now divide two distinct numbers by one fixed divisor $n$, and consider the remainders after division by $n$, called \emph{the $n$-remainder}. \begin{itemize} \item If both $n$-remainders are the same, then the difference of the two given numbers is a multiple of $n$. \item If the difference of the two given numbers is a multiple of $n$, then the two numbers leave the same $n$-remainder. \end{itemize} \noindent For example, 13 leaves $4$-remainder 1, and 5 also leaves $4$-remainder 1. The difference $13-5=8$ is a multiple of $4$. \subsection*{Cyclicity}%%%% Fix the divisor (i.e. divide always by the same number) and look at the remainder. For example, divide the numbers by 3: \begin{center} \begin{tabular}{c|c} Number & 3-remainder\\ \hline 0 & 0\\ 1 & 1\\ 2 & 2\\ 3 & 0\\ 4 & 1\\ 5 & 2\\ 6 & 0\\ 7 & 1\\ 8 & 2\\ 9 & 0\\ 10 & 1\\ 11 & 2\\ 12 & 0\\ \end{tabular} \end{center} \noindent We can go on, and obtain all possible $3$-remainders (namely, the numbers 0,1,2) that cyclically repeat. Consider another example, and divide the numbers by 4: \begin{center} \begin{tabular}{c|c} Number & 4-remainder\\ \hline 0 & 0\\ 1 & 1\\ 2 & 2\\ 3 & 3\\ 4 & 0\\ 5 & 1\\ 6 & 2\\ 7 & 3\\ 8 & 0\\ 9 & 1\\ 10 & 2\\ 11 & 3\\ 12 & 0\\ \end{tabular} \end{center} \noindent We can go on, and obtain all possible $4$-remainders (namely, the numbers $0$,$1$,$2$,$3$) that cyclically repeat.\\ \noindent In general, if the divisor is some fixed number $n$, then we see all possible $n$-remainders (namely, the numbers from $0$ to $n-1$) that cyclically repeat by increasing the dividend. \section*{The remainder games} \subsection*{The 3/4-remainder game} %%%%%% I choose a secret number, and you have to guess it with some information that I give you. \begin{itemize} \item My secret number is between $0$ and $11$, \item My secret number leaves $3$-remainder $2$. \item My secret number leaves $4$-remainder $0$. \end{itemize} How can we guess the number? \begin{itemize} \item Since the $3$-remainder $2$, the secret number is either $2$,$5$,$8$, or $11$. \item Since the $4$-remainder is $0$, the secret number is either $0$,$4$, or $8$. \end{itemize} Putting things together, the secret number is $8$!\\ \noindent \emph{Why does this 3/4-remainder game work?}\\ \noindent \emph{Firstly, the secret number is chosen among $3\times 4$ consecutive numbers.} If in the above game the secret number had been between $0$ and $50$, then the informations would not have been sufficient: the secret number could have been $8$, $20$, $32$, or $44$!\\ \noindent \emph{Secondly, we know the $3$-remainder and the $4$-remainder, and the numbers $3$ and $4$ have no common multiple between $0$ and $3\times4$.} To illustrate the importance of this fact we use a different pair of numbers. If the secret number is between $0$ and $11$ (as before), and I tell you that the $2$-remainder is $1$ and the $6$-remainder is $5$, then you cannot say if the number is $5$ or $11$! This is because $2$ and $6$ \textit{do} have a common muliple between $0$ and $2\times6$, namely, $6$ itself.\\ \noindent A related and important point is that since $3$ and $4$ have no common multiple between $0$ and $3\times4$, then they have no common factor except $1$. In the same way, since $2$ and $6$ do have a common multiple between $0$ and $2\times6$, namely $6$, they also have a common factor besides $1$, namely $2$ itself. This is why there are $2$ groups of numbers between $0$ and $2\times6$ where you can find potential solutions, and why you get both $5$ and $11$.\\ \noindent This relationship works the other way, too: if two numbers $m$ and $n$ have no common factor besides $1$, then they have no common multiple between $0$ and $mn$. \emph{As long as two numbers have no common factor besides 1, you can play a game like this}.\\ \noindent We illustrate this with another example. \subsection*{The 3/8-remainder game} %%%%%% I choose a secret number, and you have to guess it with some information that I give you. \begin{itemize} \item My secret number is between $0$ and $23$, \item My secret number leaves $3$-remainder $2$. \item My secret number leaves $8$-remainder $0$. \end{itemize} How can we guess the number? \begin{itemize} \item Because of the $3$-remainder, the secret number is either $2$, $5$, $8$, $11$, $14$, $17$, $20$, or $23$. \item Because of the $8$-remainder, the secret number is either $0$,$8$, or $16$. \end{itemize} \noindent Putting things together, you know that the secret number is $8$! \\ \noindent \emph{Why does this 3/8-remainder game work?} For the same reasons as before! Firstly, the secret number is chosen among $3\times 8$ consecutive numbers. Secondly, we know the $3$-remainder and the $8$-remainder, and the numbers $3$ and $8$ have no common factor except $1$, and thus no common multiple between $0$ and $3\times8$.\\ \noindent \emph{Trick:} If you consider the $8$-remainder first, then you are left with only 3 numbers to choose from, and you just have to select the one which leaves the correct $3$-remainder! \subsection*{The 3/4/5-remainder game}%%%%%% I choose a secret number, and you have to guess it with some information that I give you. \begin{itemize} \item My secret number is between 0 and 59. \item My secret number leaves $3$-remainder 2. \item My secret number leaves $4$-remainder 0. \item My secret number leaves $5$-remainder 4. \end{itemize} Putting things together, you know that the secret number is 44!\\ \noindent \emph{Why does this 3/4/5-remainder game work?} Firstly, the secret number is chosen among $3\times 4\times 5$ consecutive numbers. Secondly, we know the $3$-remainder, the $4$-remainder and the $5$-remainder, and any two numbers among $3$, $4$, and $5$ have no common factor. So they will have no common multiple between $0$ and $3\times4\times5=60$.\\ \noindent \emph{Trick:} Play the 4/5-remainder game first and guess the number between 0 and 19 that has the given 4-remainder and 5-remainder. The secret number is then either that number, or that number plus $20$, or that number plus $40$. You are left with only $3$ numbers, and you just have to pick the one which has the correct $3$-remainder.\\ \noindent In the above example, $4$ is the number between $0$ and $19$ that leaves $4$-remainder $0$ and $5$-remainder $4$. So we have to pick the number among $4$, $24$ and $44$ which has $3$-remainder $2$.\\ \noindent Of course there are many possible strategies to play the remainder games, and you can develop your own! \section*{Chinese Remainder Theorem/Clock} %%%%%% \subsection*{Reading the Chinese Remainder Clock} %%%%%% \begin{itemize} \item If you are able to play the 3/4-remainder game then you are able to read the hour in the Chinese Remainder Clock! Indeed the hour is a number from 0 to 11 and in the Clock you see the remainders after division by 3 and by 4.\\ \item If you are able to play the 3/4/5-remainder game then you are able to read the minutes (and the seconds) in the Chinese Remainder Clock! Indeed the minute (respectively, the second) is a number from 0 to 59 and in the Clock you see the remainders after division by 3, by 4, and by 5.\\ \item In the 24h version of the Chinese Remainder Clock then you have a 3/8-remainder game for the hour. Indeed the hour is a number from 0 to 23 and in the Clock you see the remainders after division by 3 and by 8. \end{itemize} \subsection*{The Chinese Remainder Theorem} %%%%%% \noindent The Chinese Remainder Theorem can be considered as the general theory behind the remainder games. Therefore we present it from this point of view.\\ \noindent The Chinese Remainder Theorem (in the simplified version with two numbers) is the following: \begin{quote} Consider two natural numbers $m$ and $n$, both nonzero and having no common factors. Choose freely one $m$-remainder and one $n$-remainder. Then there is exactly one natural number between $0$ and $m\times n-1$ that leaves the given remainders!\\ \end{quote} \noindent The general version of the Chinese Remainder Theorem is the following:\\ \begin{quote} Consider natural numbers $m_1,m_2,\ldots,m_n$ such that none of them is zero and no pair of them has a common factor. Choose freely one $m_1$-remainder, one $m_2$-remainder, and so on until the $m_n$-remainder. There is exactly one natural number between $0$ and $m_1\times m_2\times \ldots \times m_n-1$ that has the given remainders! \end{quote} \newpage \end{document}