# Automata and Arithmetics in Canonical Number Systems
## 2 Definitions and Results Related to Canonical Number Systems  
**Definition 1**. : _Let \(P\in\mathbb{Z}[x]\) be a monic polynomial, \(R=\mathbb{Z}[x]/P\mathbb{Z}[x]\) be the corresponding quotient ring, and let \(\varphi:\mathbb{Z}[x]\to R\) be the homomorphism \(\varphi(A)=A\mod P\). Furthermore, let \(m>1\), \(\mathcal{N}=\{n_{1},\ldots,n_{m}\}\subseteq\mathbb{Z}\), and let \(\mathcal{N}[x]\subseteq\mathbb{Z}[x]\) be the set of polynomials with all coefficients from \(\mathcal{N}\). The pair \((P,\mathcal{N})\) is called a number system, if for any \(A\in\mathbb{Z}[x]\) there exists a unique \(B\in\mathcal{N}[x]\), such that \(\varphi(A)=\varphi(B)\)._  
_The number system is called canonical, and \(P(x)\) is called a CNS polynomial if \(\mathcal{N}=\{0,1,\ldots,m-1\}\)._  
_The length of the representation of \(A\) by \(P\) is \(L(A)=L(A,P)=\deg(B)+1\)._  
**Example 1**. : _Let us consider the number system corresponding to the base-\(3\) system._  
_The base-\(3\) numeration system is, in fact, isomorphic to the polynomial system based on \(P(x)=x-3\) since the unique root of \(x-3\) is \(3\). In other words, the isomorphism arises because when we substitute \(x=3\) into any polynomial, we recover the standard evaluation in base-\(3\)._  
_Let us illustrate this with the constant_ \(16\) _as an example:_  
2. _In the classical base-\(3\) system, the representation of_ \(16\) _is obtained by dividing_ \(16\) _by_ \(3\) _repeatedly:_ 1. _[label=()]_
3. _[label=()]_
4. _[label=()]_
5. _[label=()]_
6. _[label=()]_
7. _[label=()]_
8. _[label=()]_
9. _[label=()]_
10. _[label=()]_
11. _[label=()  
_._ 2. _In the polynomial system with base_ \(x-3\)_, we essentially perform the same 'division with remainder' process, but in the context of polynomials. Here, the constant_ \(16\) _must be represented by a polynomial_ \(B(x)=a_{2}x^{2}+a_{1}x+a_{0}\) _(with_ \(a_{i}\in\{0,1,2\}\)_) such that_ \(B(3)=16\)_. Analogously to the integer numeration system, we repeatedly divide_ \(16\) _by_ \(x-3\)_._ 1. _To find the last digit, we execute the 'integer' division_ \(16\div(x-3)\)_. Actually, we solve the equation_ \(16=q\cdot(x-3)+s\cdot x+r\)_, where_ \(r\in\{0,1,2\}\)_. The only solution is_ \(q=-5\)_,_ \(s=5\) _and_ \(r=1\)_. Hence, the last digit is_ \(1\)_, and we should represent_ \(5x\) _in the system._ 2. _For the second digit, we solve_ \(5=q\cdot(x-3)+s\cdot x+r\)_, with_ \(r\in\{0,1,2\}\)_. The only solution is_ \(q=-1\)_,_ \(s=1\)_, and_ \(r=2\)_._ 3. _Finally, we should solve_ \(1=q\cdot(x-3)+s\cdot x+r\)_, with_ \(r\in\{0,1,2\}\)_. The only solution is_ \(q=0\)_,_ \(s=0\)_, and_ \(r=1\)_. Since_ \(s=0\)_, thus there is no more carry in the computation, so the algorithm terminates._ _Thus, the polynomial representation of_ \(16\) _is_ \(x^{2}+2x+1\)_, exactly as in the classical base-_\(3\) _system._  
**Remark 1**. : _Note that the system in Example 1 is not a number system in the general sense of Definition 2 since negative integers cannot be represented._  
**Example 2**. : _Now, consider the base system (\(-3\)) number, which corresponds to the polynomial \(P(x)=x+3\). This system has the same digits \(\mathcal{N}=\{0,1,2\}\), just like the base-\(3\) system. We may observe that in the system with base \((-3)\), we can represent all integers, both negative and non-negative._  
_Express \(16\) once more in this numeration system:_  
1. _Again, we execute repeated division by_ \(-3\) _:_ 1. \(16\div-3=-5\) _with remainder_ \(16-(-5)\cdot(-3)=1\quad\Rightarrow\) _units digit is_ \(1\)_._ 2. \(-5\div-3=2\) _with remainder_ \(5-2\cdot(-3)=1\quad\Rightarrow\) _next digit is_ \(1\)_._ 3. \(2\div-3=0\) _with remainder_ \(2-0\cdot 3=2\quad\Rightarrow\) _highest digit is_ \(2\)_._ _So we obtain the digits_ \(2,1,1\)_, i.e.,_ \(16=211_{-3}\)_._ 2. _In the polynomial system with base_ \(x+3\)_, we execute similar steps to those in the previous example. Here, the constant_ \(16\) _must be represented by a polynomial_ \(B(x)=a_{2}x^{2}+a_{1}x+a_{0}\) _(with_ \(a_{i}\in\{0,1,2\}\)_) such that_ \(B(-3)=16\)_._ 1.