# Automata and Arithmetics in Canonical Number Systems
## 2 Definitions and Results Related to Canonical Number Systems
_To find the last digit, 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=-2\)_,_ \(s=2\)_, and_ \(r=1\)_._ 3. _Finally, we should solve_ \(2=q\cdot(x+3)+s\cdot x+r\)_, with_ \(r\in\{0,1,2\}\)_. The only solution is_ \(q=0\)_,_ \(s=0\)_, and_ \(r=2\)_. Since_ \(s=0\)_, thus there is no more carry in the computation, so the algorithm terminates._ _Thus, the polynomial representation of_ \(16\) _is_ \(2x^{2}+x+1\)_._  
**Remark 2**. : _The system in Example 2 is indeed a valid number system since it can represent both positive and negative integers. For instance, \(-1=12_{-3}\)._  
**Remark 3**. : _If \((P,\mathcal{N})\) is a number system, then the reduced homomorphism \(\varphi:\mathcal{N}[x]\to R\) is an isomorphism._  
[PERSON] in [4] proved that if the coefficients of \(P\) are increasing, then there exists a corresponding canonical number system. We reformulate it in the following theorem. **Theorem 1**. : _Let \(P\in\mathbb{Z}[x]\) be a monic polynomial with \(\deg(P)=d\), and \(P(x)=p_{d}x^{d}+\cdots+p_{0}\) be such that \(1=p_{d}\leq p_{d-1}\leq\cdots\leq p_{0}\) with \(2\leq p_{0}\). If \(P\) is not divisible by a cyclotomic polynomial, then \(P\) is a CNS polynomial._  
**Example 3**. : _Let \(P(x)=x^{2}+x+3\) and let \(\alpha\) be one of its roots. By Theorem 1, \((P,\{0,1,2\})\) is a canonical number system. The corresponding numeration system of \(\mathbb{Z}[\alpha]\) has the base \(\alpha\), with digits \(\{0,1,2\}\). This polynomial defines a number system over the algebraic integers, extending the idea of canonical number systems to the algebraic integers \(\mathbb{Z}[\alpha]\)._  
_Now, we consider the only case when calculating the digits in the polynomial number system. Again, we want to express \(16\) in this system._  
1. _To find the last digit, we solve the equation_ \(16=q\cdot(x^{2}+x+3)+s\cdot x+r\)_, where_ \(r\in\{0,1,2\}\)_. The only solution is_ \(q=5\)_,_ \(s=-5x-5\)_, and_ \(r=1\)_. Hence, the last digit is_ \(1\)_, and we should represent_ \(-5x^{2}-5x\) _in the system._
2. _For the second digit, we solve_ \(-5x-5=q\cdot(x^{2}+x+3)+s\cdot x+r\)_, with_ \(r\in\{0,1,2\}\)_. The only solution is_ \(q=-2\)_,_ \(s=2x-3\)_, and_ \(r=1\)_._
3. _Next, we should solve_ \(2x-3=q\cdot(x^{2}+x+3)+s\cdot x+r\)_, with_ \(r\in\{0,1,2\}\)_. The only solution is_ \(q=-1\)_,_ \(s=x+3\)_, and_ \(r=0\)_. This yields that the next digit is_ \(0\)_._
4. _Now, we should solve_ \(x+3=q\cdot(x^{2}+x+3)+s\cdot x+r\)_, with_ \(r\in\{0,1,2\}\)_. The only solution is_ \(q=1\)_,_ \(s=-x\)_, and_ \(r=0\)_. Hence, the next digit is again_ \(0\)_._
5. _Then, we solve_ \(-x=q\cdot(x^{2}+x+3)+s\cdot x+r\)_, with_ \(r\in\{0,1,2\}\)_. The only solution is_ \(q=0\)_,_ \(s=-1\)_, and_ \(r=0\)_. The next digit is again_ \(0\)_._
6. _In the next step we solve_ \(-1=q\cdot(x^{2}+x+3)+s\cdot x+r\)_, with_ \(r\in\{0,1,2\}\)_. The only solution is_ \(q=-1\)_,_ \(s=x+1\)_, and_ \(r=2\)_. The next digit is_ \(2\)_._
7. _Now, we solve_ \(x+1=q\cdot(x^{2}+x+3)+s\cdot x+r\)_, with_ \(r\in\{0,1,2\}\)_. The only solution is_ \(q=0\)_,_ \(s=1\)_, and_ \(r=1\)_. The next digit is_ \(1\)_._
8. _Finally, we should solve_ \(1=q\cdot(x^{2}+x+3)+s\cdot x+r\)_, with_ \(r\in\{0,1,2\}\)_. The only solution is_ \(q=0\)_,_ \(s=0\)_, and_ \(r=1\)_. Hence, the first digit is again_ \(1\)_, and the algorithm terminates._  
_The iterations of the algorithm are displayed in Table 1. Column \(N\) refers to the remaining value we should represent in the system, while \(q\), \(s\), and \(r\) are as in the description._  
_We obtain that the representation of \(16\) in the number system \((x^{2}+x+3,\{0,1,2\})\) is \(11\,200\,011_{(x^{2}+x+3)}\).