\section{Characteristic and Modulo arithmetic}\label{SectionCharacteristics} \memo{The most non-trival theorem in this section is a known result} \subsection{Chracteristics} Recall that a characteristic of a ring is a minimum positive integer $n$ such that \[0=\underbrace{1+1+\dots +1}_{n \text{ times}},\] if such $n$ exists, and otherwise $0$. We will define similar notion to riegs. However, the exactly same definition does not work, since if we have a positive integer $n$ such that $0=n$, then $n-1$ is the additive inverse of $1$ and the rieg should be isomorphic to the trivial rieg (Proposition \ref{PropositionMinusOne}). We adopt a relaxed definition: \begin{definition}[Characteristic] For a rieg $R$, its characteristic $\ch R$ is a minimum pair \memo{Clarify the meaning of \dq{minimum.} But I think there is no room for confusion...?} $(a,b)$ of non-negative integer $a$ and a positive integer $b$ such that \[ \underbrace{1+\dots +1}_{a \text{ times}}= \underbrace{1+\dots +1}_{a \text{ times}}+ \underbrace{1+\dots +1}_{b \text{ times}}. \] If there does not exists such a pair, the characteristic is defined to be $\chz$. \end{definition} \begin{example}[Trivial rieg] The characteristic of the trivial rieg is $(0,1)$. Conversely, if the characteristic of a rieg $R$ is $(0,1)$, then $0=1$ and $R$ turns out to be trivial. More generally, if the characteristic of $R$ is $(0,b)$, then we have $0=1+\dots+1$ and $b-1 =-1$. Then we can conclude that $R$ is trivial and $b=1$. No rieg has characteristic $(0,b)$ for $b\geq2$. \end{example} \begin{example}[Overflow riegs] \memo{later!} \end{example} \begin{example}[Parity riegs] \memo{later!} \end{example} After reading the definition and examples, you may ask two questions: \dq{Is this definiton natural?} and \dq{Which pair $(a,b)$ can be realized as a characteristic of a rieg?} In the remaining part of this subsection, we will focus on the first question. The second question is the main topic of the next subsection.\memo{This turned out to be a known result.} \subsubsection*{Is this definiton natural?} From an abstract point of view, this defnition is quite natural. In fact, we can \dq{deduce} this definition from a general setting. For an arbitrary equational theory $T$, we can define a notion of \dq{characteristic} of $T$-algebra as follows. Recall that the category of $T$-algebras admits the (surjection, injection) factorization system, or (regular epi, mono) factorization in terms of category theory. \memo{reference} % and the initial object $I$. Therefore, for each $T$-model $A$, we can canonically associate a quotient $Q$ of the initial $T$-algebra $I$ obtained by factorizing the unique homomorphism \[I\twoheadrightarrow Q \rightarrowtail A.\] In the case of rings, the associated quotient is $\Z /n\Z$, where $n$ is the characteristic of the given ring $A$. So this abstract definition is a generalization of the notion of characteristics. \memo{I don't claim that this is the most natural gereralization.} In the case of pointed groups, which are groups with a distingished element, the characteristic of a pointed group $(G,g)$ is $\Z /n \Z$, where $n$ is the order of the element $g\in G$. In the case of pointed $\Q$-algebras, the characteristics of the pointed $\Q$-algebra $(\overline{\Q},\alpha)$ is $\Q[x]/(f(x))$, where $f(x)$ is the minimum polynomial of $\alpha$. Then, how about the case of riegs? The initail rieg is the rieg of natural numbers. \begin{proposition} The rieg of natural numbers $\N$ is the initial object in the category of riegs. \end{proposition} Therefore, what we need to do is classify the quoteits of $\N$. The starting point is the classification of quotients of the additive monoid $\N$. % By the classification of quotients of the additive monoid $(\N,0,+)$, It is known that all non-trivial congruence $\sim$ on $(\N,0,+)$ is of the form \[n \sim m \iff (n=m)\lor ((n,m\geq a) \land (n\equiv m \mod{b})) \] % \[n \sim m \iff (n\equiv m \mod{b})\land ((n=m)\lor (n,m\geq a)) \] with $a\geq0$ and $b>0$. \memo{reference} Let $\Mr{a}{b}$ denote the quotient additive monoid. It is quicker to look at the picture of $\Mr{3}{4}$ than to look at the logical symbols (Figure \ref{PictureModuleRieg}). \begin{figure} \begin{shaded} \centering \begin{tikzpicture} [scale = 2] \fill[black] (0,2) circle (0.06) node[above]{}; \fill[black] (1,2) circle (0.06) node[above]{}; \fill[black] (2,2) circle (0.06) node[above]{}; \fill[black] (3,2) circle (0.06) node[above]{}; \fill[black] (4-0.36,1+0.36) circle (0.06) node[above]{}; \fill[black] (3,0+0.36+0.36) circle (0.06) node[above]{}; \fill[black] (2+0.36,1+0.36) circle (0.06) node[above]{}; \draw[black, thick](3,1+0.36) circle (0.64); \draw[black, thick] (0,2) -- (3,2); \end{tikzpicture} \caption{Picture of $\Mr{3}{4}$} \label{PictureModuleRieg} \end{shaded} \end{figure} For example, (the underlying additive monoid of) the trivial rieg is $\Mr{0}{1}$, the truth value rieg $\2$ is $\Mr{1}{1}$, and the parity rieg is $\Mr{1}{2}$. \memo{Overflow riegs} \begin{proposition} For any $a\geq 0$ and $b>0$, $\Mr{a}{b}$ admits the unique rig structure such that the canonical surjection $\N \twoheadrightarrow \Mr{a}{b}$ is a rig homomorphism. The rieg structure on the rig $\Mr{a}{b}$ is unique, if it exists. Every quotient of $\N$ is $\N$ itself or otherwise of the form of $\Mr{a}{b}$ for some $a\geq 0$ and $b>0$. \end{proposition}\memo{Modify this later..} \begin{proof} \end{proof} With those proof, we can rephrase the definition of the characteristics. % \begin{proposition} % For a rieg $R$ with characteristic $\ch R =(a,b)$, the unique rieg homomorphism $\N \to R$ is factored as % \[\N\twoheadrightarrow \Mr{a}{b} \rightarrowtail R.\] % The characteristic of $R$ is $0$ if and only if $\N \to R$ is injetive. % \end{proposition} \begin{proposition}[Chraracteristic, in terms of the quotients of $\N$] For a rieg $R$ and the (surjection, injection) factorization of the unique morphism $\N \to \R$, \[\N\twoheadrightarrow Q \rightarrowtail R,\] \begin{itemize} \item $Q\cong \Mr{a}{b} \iff \ch R = (a,b)$ \item $Q \cong \N \iff \ch R = \chz.$ \end{itemize} \end{proposition} % \memo{Uniqueness of rieg structure on $\Mr{a}{b}$, if it exists.} \subsubsection*{Which pair $(a,b)$ can be realized as a characteristic of a rieg?} \memo{For semirings, every value can be realized.} % \begin{remark}[Is this definition natural?] % \end{remark} % For example, a rieg $R$ with characteristic $\ch R= (0,1)$ is a rieg with $0=1$, which is the trivial rieg. \subsection{Classification of the quotients of $\N$} \memo{On the terminology \dq{modulo riegs}} Before we get into the theoretical considerations, let us list a few examples. \begin{example}[$\N$ itself] $\N$ itself is a trivial modulo rieg. \end{example} \begin{example}[Trivial rieg] A singleton $\{\ast\}$ has a unique rieg structure. We call it \emph{trivial rieg}. It is the terminal rieg and can be regarded as a modulo rieg by the unique homomorphism $\N \to \{\ast\}$. \end{example} \begin{example}[Truth value rieg] As we will see later, the set of truth values $\2 = \{\bot, \top\}$ has a natural rieg structure, as $(\2, \bot, \top, \lor, \land, \leftarrow)$. % \begin{itemize} % \item $0$ is the $\bot$ % \item $1$ is $\top$ % \item $x+y$ is $x \lor y$ % \item $xy$ is $x\land y$ % \item $x^y$ is $y \to x$ % \end{itemize} The proposition \[\text{IsPositive}\colon \N \twoheadrightarrow \2\] is a surjection and defines a modulo rieg. % The set $\{\text{zero},\text{positive}\}$ and the natural surjection $\N \to \{\text{zero},\text{positive}\}$ induces a rieg structure on $\{\text{zero},\text{positive}\}$. % For several reasons, we call this rieg $\2$. \end{example} \begin{example}[Parity rieg] As a bit more non-trivial example, the natural surjection \[\N \twoheadrightarrow \{0, \text{positive odd}, \text{positive even} \}\] induces a modulo rieg. We call it the \emph{parity rieg}. \end{example} Before stating the classification theorem, we introduce two terminologies. \begin{definition}[Tame number] A positive integer $n$ is said to be \emph{tame} if, for any prime factor $p$ of $n$, $p-1$ also divides $n$. \end{definition} The list of tame numbers begins as: \[1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 32, 36, 40, 42, 48, 54, 60, 64, 72, 80, 84, 96, 100, 108, \dots.\] Notice that there are infinitely many tame numbers since $2^k$ is tame. The reason for considering tame numbers is the following algebraic paraphrase. Simply put, \dq{$n$ is tame if and only if exponentials are also well-defined by $\mod{n}$.} \begin{lemma}[Algebraic characterization of tame numbers]\label{LemmaAlgebraicCharacterizationOfTameNumbers} For a positive integer $n$, the following conditions are equivalent: \begin{enumerate} \item $n$ is tame. \item for any $x \in (\Z/n\Z)^{\times}$, $x^n \equiv 1 \mod{n}.$ \end{enumerate} \end{lemma} \begin{proof} First, we will prove (2), assuming (1). Let $n={p_1}^{k_1}\dots {p_l}^{k_l}$ be the prime factorization of $n$. Then we have a group isomorphism \[ (\Z/n\Z)^{\times} \cong (\Z/ {p_1}^{k_1} \Z)^{\times}\times \dots \times (\Z/ {p_l}^{k_l} \Z)^{\times}. \] Therefore, it is enough to prove that, for any $1\leq i \leq l$ and $x \in (\Z/ {p_i}^{k_i} \Z)^{\times}$, $x^n \equiv 1 \mod{{p_i}^{k_i}}$. But this immediately follows from tameness of $n$, since $\# (\Z/ {p_i}^{k_i} \Z)^{\times} = (p-1)p^{k_i -1}$, which divide $n$. Conversely, we will prove (1) from (2). Let $p$ be an odd prime factor of $n$. (The case where $p=2$ is obvious.) The multiplicative group $(\Z/n\Z)^{\times}$ has a element $x$ whose order is $p-1$, because $(\Z/ {p}^{k} \Z)^{\times}$ is cyclic. \footnote{This is not obvious by definition, but well-known.} By the assumption $x^n \equiv 1 \mod n$, we have $p-1 \mid n$. % \[(\Z/ p^{k_l} \Z)^{\times} \simeq \Z/(p-1)p^{}\] \end{proof} \begin{remark}[Carmichael numbers] This is reminiscent of Carmichael numbers, which are defined as a positive integer $n$ that satisfies \begin{itemize} \item for any $x \in (\Z/n\Z)^{\times}$, $x^{n-1} \equiv 1 \mod{n}.$ \end{itemize} Although the definitions are very similar, the only tame Carmichael numbers are obviously only trivial ones, namely $1$ and $2$. In light of these facts, rather than the boring name \dq{tame numbers,} perhaps we should call them anti-Carmichael numbers (?) \end{remark} \begin{definition}[Dimention] A \emph{dimension} of a positive integer $n$ is the maximum value of the exponent that appears in the prime factorization of $n$. It is denoted by $\di(n)$. \end{definition} For example, the dimentions of small numbers are $\di(1)=0, \di(2)=1, \di(3)=1, \di(4)=2, \di(5) = 1, \di(6)=1, \di(7)=1, \di(8)=3$. \begin{remark}[Radical]\label{RemarkRadical} A dimension is inextricably linked to the notion of \emph{radicals} of positive integers. \memo{ABC conjecture} Recall that the radical of a positive integer $n$, often denoted by $\rad(n)$, is a positive integer obtained by replacing all exponents in the prime factorization of $n$ by $1$. For example, $\rad(5400)=\rad(2^3\cdot 3^3\cdot 5^2)=2\cdot 3\cdot 5 = 30$. The dimension $\dim(n)$ is the minimum $d$ such that $n$ divide $\rad(n)^d$, and conversely $\rad(n)$ is the maximum $1$-dimensional divisor of $n$. \end{remark} \begin{theorem}[Classification of modulo riegs \cite{burris1993tarski}]\label{TheoremPossibleChar} For $a\geq 0$ and $b>0$, $\Mr{a}{b}$ has a rieg structure if and only if $b$ is a tame number whose dimension is at most $a$. % \begin{enumerate} % \item $a\geq \di(b)$ % \item $b$ is tame. % \end{enumerate} \end{theorem} \begin{proof} Assuming $\Mr{a}{b}$ has a rieg structure, we will prove $b$ is a tame number whose dimension is at most $a$. Let $[x] \in \Mr{a}{b}$ denote the equivalence class that contains $x\in \N$. For an arbitrary natural number $x$ that is coprime with $b$, we have \[ [x^{a+b}]=[x]^{[a+b]}=[x]^{[a]}=[x^{a}], \] hence \[x^{a+b} \equiv x^{a} \mod{b},\] and \[x^b \equiv 1 \mod{b}.\] By Lemma \ref{LemmaAlgebraicCharacterizationOfTameNumbers}, $b$ is tame. Next, we move on to the dimension of $b$. For any non-negative integer $m\geq 0$, we have \[[\rad(b) ^a]=[\rad(b)]^{[a]}=[\rad(b)]^{[a+mb]}=[\rad(b)^{a+mb}],\] and \[\rad(b) ^a\equiv \rad(b) ^{a+mb} \mod{b}.\] By taking a sufficiently large $m$ such that $a+mb\geq \dim(b)$, we obtain \[\rad(b) ^a\equiv 0 \mod{b},\] equivalently, $a\geq \dim(b)$. Conversely, assuming that $b$ is a tame number whose dimension is at most $a$, we will prove the rig $\Mr{a}{b}$ has a rieg structure. It is enough to prove that $\ex$ is well-defined.\footnote{Here, we implicitly use the fact of universal algebra: if an equivalence relation is compatible with all operations, then its quotient set has the unique (same type of) algebraic structure such that the canonical surjection is homomorphic.} If $a=0$, then $b=1$, and this case is trivial. In the rest of the proof, we assume $a>0$. We begin with the easier case: assuming $[x_0]=[x_1]$, we will prove $[{x_0} ^{y}]=[{x_1}^{y}]$. If $x_0 = x_1$ or $y=0$, this is trivial. Suppose $x_0 < x_1$ and $y>0$. Since $x_0 \neq x_1$, we have $a\leq x_0,x_1$ and ${x_0} \equiv {x_1} \mod{b}$. Since $y>0$, we have $a\leq x_0,\leq {x_0}^y\leq {x_1}^{y}$. As a result, we obtian $a\leq {x_0}^y, {x_1}^{y}$ and ${x_0}^y \equiv {x_1}^{y}\mod{b}$, which mean $[{x_0} ^{y}]=[{x_1}^{y}]$. Lastly, assuming $[y_0]=[y_1]$, we will prove $[x ^{y_0}]=[x^{y_1}]$. If $y_0=y_1$, this is trivial. Therefore, we can assume $0