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

$a=s_n{b}^n+s_{n-1}{b}^{n-1}+\mathrm{\dots }+s_{1}b+s_0,$(1)

where the integers $s_i$ satisfy  $0\leqq s_i\leqq b-1$  and  $s_n\ne 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}\mathrm{\dots }{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

$a=s_n{b}^n+r_1$

$r_1=s_{n-1}{b}^{n-1}+r_2$

$r_2=s_{n-2}{b}^{n-2}+r_3$

$\mathrm{\hspace{1em}\hspace{1em}}\mathrm{⋮}$

$r_{n-2}=s_2{b}^2+r_{n-1}$

$r_{n-1}=s_{1}b+s_0$

Adding these equations yields the equation (1) with  $0\leqq s_i\leqq b-1$,  $s_n\ne 0$.

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

$$a=t_m{b}^m+t_{m-1}{b}^{m-1}+\mathrm{\dots }+t_{1}b+t_0$$

with  $0\leqq t_i\leqq s-1$,  $b_m\ne 0$.  The equality

$s_n{b}^n+s_{n-1}{b}^{n-1}+\mathrm{\dots }+s_{1}b+s_0=t_m{b}^m+t_{m-1}{b}^{m-1}+\mathrm{\dots }+t_{1}b+t_0$(2)

immediately implies

$$s_0\equiv t_0(modb),\text{i.e.}\mathit{\hspace{1em}}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(mod{b}^2)$, whence $s_1\equiv t_1(modb)$,  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,\mathrm{\dots }$  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\mathrm{\cdots }{b}_i$$

where the integers $s_i$ satisfy    and  $s_n\ne 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