Giancarlo Rinaldo edited friends.tex  about 6 years ago

Commit id: 916b2d2684d382124bdc66331796d94ec5128184

deletions | additions      

       

\[  7x=9 \mod 12.  \]  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 $\ZZ_{12}$ are the ones that are not coprime with $12$, namely the elements in $a\in\ZZ_{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 invertible:  $\{1,5,7,11\}$. Moreover in $\ZZ_7$ they are all but $0$. Having the information about the The  number of invertible elements in $\ZZ_m$ is a fundamental information. The function that given as input $m$, the number of  elements of $\ZZ_m$, give as output the number of invertile invertible  elements in $\ZZ_m$ is called Euler function, namely \[  \phi(m)=\vert \{a\in \ZZ_m \mbox{ and a is invertible}\}\vert.  \]  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 give given  number $m$ to compute $\phi(m)$. By observation above, we may deduce that when $m$ is a prime number the set $\ZZ_m$ is a field. In fact all the non-zero elements are invertible, as in $\ZZ_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 $\ZZ_7$.  The powers of $3$ are  \[  3, 3^2=9\cong 2, 3^3=3^2\cdot 3\cong 2\cdot 3=6  \] 

\end{picture}  \caption{$C_8(\{2,3\}$) e $C_8(\{1,4\})$.} \label{C8}   \end{figure}   This has a precise meaning from a mathematical point of view, the concept of \emph{characteristic}.\\  Given a field (in our case $\Fb$), it can happen that   some positive\footnote{notice: positive means \emph{different} from $0$!!} integer numbers, multiplied to all the elements of the field, give $0 $ as   result (in our case, we saw that $2$ has this property).\\  The smallest such number $p$ - if it exists - is called \emph{characteristic} of the field (the characteristic is $p=2$ in the field $\Fb$). If there are no number with this properties, we say that the field has characteristic $p=0$.  \begin{Exercise}\label{ProofChar}  We have already observed that $2\cdot 0 = 2 \cdot 1=0$, so $2$ is one of the numbers that multiplied to all the elements of the field of bits,   give $0 $ as result. Can you prove that $2$ is actually the characteristic of $\Fb$?  \end{Exercise}  \begin{Exercise}\label{MaxiSum}  Compute the following operations in $\Fb$:  \begin{itemize}  \item $1+1+1+1+1+0+1+1+0+1=?$  \item $1+1+1+0+1+1+1+0+1+1+1=?$  \item $\underbrace{1+1+...+1}_{1235 \textrm{ times}}=?$  \item $\underbrace{1+1+...+1}_{15754 \textrm{ times}}=?$  \item $1245 \cdot 1=?$  \item $2482 \cdot 1=?$  \item $1234 \cdot 0=?$  \end{itemize}  Can you conclude, deriving a general rule for computing multiples of bits?  \end{Exercise}