There exist particular phenomena as those related with time that have a kind of ciclicity. We focus on two examples
The days of the week, or if you like music, the musical notes, which are \(7\);
The hours of a day that we assume are \(12\), as in an analog clock.
The two clocks in the picture represent exactly these two cases. These examples are similar in some sense. In fact we have that the first day of a week is Monday, the \(8^{th}\) is Monday again. The seventeenth is Wednesday. In this case we have \(2\) tours around the clock and the remainder is \(3\). That is
\begin{equation} 17=2\times 7+3.\nonumber \\ \end{equation}The remainder, namely \(3\), is the number of interest for our purpose. This is nothing but an application of division algorithm. Focus on the second clock, the one with \(12\) hours, and suppose we want to find what is the \(26^{th}\) hour. We have also in this case two tours around the clock and then the remainder is \(2\), that is
\begin{equation} 26=2\times 12+2.\nonumber \\ \end{equation}Obviously the remainder depends on how many are the hours the clock. Hence every number has a unique representation after fixing the number of hours. Because of this reduction we always assume that the labelling of the hours is exactly
\begin{equation} \mathbb{Z}_{n}=\{0,1,2,\ldots,n-1\}\nonumber \\ \end{equation}where \(n\) is the number of the hours of the clock, and \(\mathbb{Z}_{n}\) is the set representing the labelling of the hours. Over these clocks we can define a very nice arithmetic that is called the clock arithmetic, or modular arithmetic. That is we can enrich the set of ”hours” with addition and multiplication in a natural way. Thus we can add or multiply the numbers in the standard way and then apply the division with respect to the fixed hours and find the remainder observing that the result belongs to \(\mathbb{Z}_{n}\). As for the case \(\mathbb{F}_{2}\) we represent the tables of the two operations on \(\mathbb{Z}_{7}\) and \(\mathbb{Z}_{12}\). First of all we consider the sum.
\begin{equation} \nonumber \\ \end{equation}In both clocks the sum is nothing but a rotation of the first row by one element. For example adding \(3\) to each element of the first row we have a rotation by \(3\) elements. in particular the \(4\) in the first row becomes
\begin{equation} 3+4=7\mod 7=0\mod 7.\nonumber \\ \end{equation}Where \(\mod\) represents the remainder of the division by \(7\). The other follows according to this rule.
Now focus on the multiplication’s tables.
The two clocks behave in different ways. In \(\mathbb{Z}_{7}\) the multiplication produce a much random table, but, in each row we find al the elements of \(\mathbb{Z}_{7}\). If we study the table of \(\mathbb{Z}_{12}\) there are some rows that are complete some other not. That is the second clock has a pathological behavior that the first clock does not have. For example suppose we want to solve the following equation
\begin{equation} 9x=0\mod 12.\nonumber \\ \end{equation}There are \(3\) numbers in the set of hours that give as a solution and these are \(0\), \(4\) and \(8\). That is not so nice. Now suppose we want to solve the following equation
\begin{equation} 9x=1\mod 12.\nonumber \\ \end{equation}If you consider each multiple of 9 modulo 12 is in the set of hours \(\{0,3,6,9\}\) hence the equation has no solution. In this case we say that the equation do not satisfy the ”cancellation” property. In fact in a ”standard” equation similar to the first one we can multiply \(9\) by its inverse, getting rid of the \(9\), and obtaining the unique solution \(0\). In fact by the table we observe that there are not multiple of \(9\) that gives \(1\). That is \(9\) is not invertible and has not a regular behaviour. Moreover if we have the equation
\begin{equation} 7x=0\mod 12.\nonumber \\ \end{equation}there exists the unique solution \(x=0\), and with respect to the equation
\begin{equation} 7x=9\mod 12.\nonumber \\ \end{equation}there is a unique solution, that is \(x=3\). It is not difficult to observe that the elements that are not regular in the set \(\mathbb{Z}_{12}\) are the ones that are not coprime with \(12\), namely the elements in \(a\in\mathbb{Z}_{12}\) such the greatest common divisor with \(12\) is not \(1\). They are \(\{2,3,4,6,8,9,10,12=0\}\). The remaining elements, the ones whose greatest common divisor with \(12\) is \(1\), are invertible: \(\{1,5,7,11\}\). Moreover in \(\mathbb{Z}_{7}\) they are all but \(0\). The number of invertible elements in \(\mathbb{Z}_{m}\) is a fundamental information. The function that given as input \(m\), the number of elements of \(\mathbb{Z}_{m}\), give as output the number of invertible elements in \(\mathbb{Z}_{m}\) is called Euler function, namely
\begin{equation} \phi(m)=|\{a\in\mathbb{Z}_{m}\mbox{ and a is invertible}\}|.\nonumber \\ \end{equation}Hence \(\phi(7)=6\) and \(\phi(12)=4\). In general if \(m\) is a prime number \(\phi(m)=m-1\). But it is hard for a given number \(m\) to compute \(\phi(m)\).
By observation above, we may deduce that when \(m\) is a prime number the set \(\mathbb{Z}_{m}\) is a field. In fact all the non-zero elements are invertible, as in \(\mathbb{Z}_{7}\). Moreover multiplying two non-zero elements we obtain another non-zero element.
Another particular fact about these fields, is that exist elements whose powers cover all the non-zero elements of thield itself. As an example consider the elements \(3\) and \(5\) in \(\mathbb{Z}_{7}\). The powers of \(3\) are
\begin{align} 3\notag \\ 3^{2}\equiv 9\equiv 2\notag \\ 3^{3}\equiv 3^{2}\cdot 3\equiv 2\cdot 3\equiv 6\notag \\ 3^{4}\equiv 3^{3}\cdot 3\equiv 6\cdot 3\equiv 4\notag \\ 3^{5}\equiv 3^{4}\cdot 3\equiv 4\cdot 3\equiv 5\notag \\ 3^{6}\equiv 3^{5}\cdot 3\equiv 5\cdot 3\equiv 1\notag \\ \end{align}The powers of \(5\) are
\begin{align} 5\notag \\ 5^{2}\equiv 25\equiv 4\notag \\ 5^{3}\equiv 5^{2}\cdot 5\equiv 4\cdot 5\equiv 6\notag \\ 5^{4}\equiv 5^{3}\cdot 5\equiv 6\cdot 5\equiv 2\notag \\ 5^{5}\equiv 5^{4}\cdot 5\equiv 2\cdot 5\equiv 3\notag \\ 5^{6}\equiv 5^{5}\cdot 5\equiv 3\cdot 5\equiv 1\notag \\ \end{align}Prove that all the elements of \(\mathbb{Z}_{7}\) different from \(3\) and \(5\) are not primitive.