uniqueness of digital representation

Theorem.  Let the positive integer $b$ be the base of a http://planetmath.org/node/3313positional digital system.  Every positive integer $a$ may be represented uniquely in the form

 $\displaystyle a\;=\;s_{n}b^{n}+s_{n-1}b^{n-1}+\ldots+s_{1}b+s_{0},$ (1)

where the integers $s_{i}$ satisfy  $0\leqq s_{i}\leqq b\!-\!1$  and  $s_{n}\neq 0$.

The theorem means that the integer $a$ may be represented e.g. in the http://planetmath.org/node/9839decimal system in the form

 $s_{n}\,s_{n-1}\ldots s_{1}\,s_{0}$

in one and only one way.

Proof.  Let $b^{n}$ be the highest integer power of $b$ not exceeding $a$.  By the division algorithm for integers, we obtain in succession

 $\displaystyle a\;\;\,=\;s_{n}b^{n}+r_{1}$ $\displaystyle(0 $\displaystyle r_{1}\,\;=\;s_{n-1}b^{n-1}+r_{2}$ $\displaystyle(0\leqq s_{n-1} $\displaystyle r_{2}\,\;=\;s_{n-2}b^{n-2}+r_{3}$ $\displaystyle(0\leqq s_{n-2} $\displaystyle\qquad\vdots$ $\displaystyle r_{n-2}\;=\;s_{2}b^{2}+r_{n-1}$ $\displaystyle(0\leqq s_{2} $\displaystyle r_{n-1}\;=\;s_{1}b+s_{0}$ $\displaystyle(0\leqq s_{1}

Adding these equations yields the equation (1) with  $0\leqq s_{i}\leqq b\!-\!1$,  $s_{n}\neq 0$.

For showing the uniqueness of (1) we suppose also another

 $a\;=\;t_{m}b^{m}+t_{m-1}b^{m-1}+\ldots+t_{1}b+t_{0}$

with  $0\leqq t_{i}\leqq s\!-\!1$,  $b_{m}\neq 0$.  The equality

 $\displaystyle s_{n}b^{n}+s_{n-1}b^{n-1}+\ldots+s_{1}b+s_{0}\;=\;t_{m}b^{m}+t_{% m-1}b^{m-1}+\ldots+t_{1}b+t_{0}$ (2)

immediately implies

 $s_{0}\;\equiv\;t_{0}\pmod{b},\quad\mbox{i.e.}\quad b\mid s_{0}\!-\!t_{0}.$

Since now  $|s_{0}\!-\!t_{0}|\leqq b\!-\!1$,  we infer that  $s_{0}\!-\!t_{0}=0$  and thus  $t_{0}=s_{0}$.  Consequently, we can then infer from (2) that  $s_{1}b\equiv t_{1}b\pmod{b^{2}}$, whence  $s_{1}\equiv t_{1}\pmod{b}$,  and as before,  $t_{1}=s_{1}$.  We may continue in manner and see that always  $t_{i}=s_{i}$, whence also  $m=n$.  Accordingly, the both are identical. Q.E.D.

Remark.  There is the following generalisation of the theorem.  — If we have an infinite sequence$b_{1},\,b_{2},\,\ldots$  of integers greater than 1, then $a$ may be represented uniquely in the form

 $a\;=\;\sum_{i=0}^{n}s_{i}b_{1}b_{2}\cdots b_{i}$

where the integers $s_{i}$ satisfy  $0\leqq s_{i}  and  $s_{n}\neq 0$.  Cf. the factorial base.

 Title uniqueness of digital representation Canonical name UniquenessOfDigitalRepresentation Date of creation 2013-03-22 18:52:16 Last modified on 2013-03-22 18:52:16 Owner pahio (2872) Last modified by pahio (2872) Numerical id 15 Author pahio (2872) Entry type Theorem Classification msc 11A63 Classification msc 11A05 Synonym uniqueness of decimal representation Synonym digital representation of integer Related topic UnambiguityOfFactorialBaseRepresentation Related topic UniquenessOfFourierExpansion Related topic UniquenessOfLaurentExpansion Related topic ZeckendorfsTheorem Related topic RepresentationOfRealNumbers