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<s_{n}<b,\quad 0\leqq r_{1}<b^{n}),$
	$\displaystyle r_{1}\,\;=\;s_{n-1}b^{n-1}+r_{2}$	$\displaystyle(0\leqq s_{n-1}<b,\quad 0\leqq r_{2}<b^{n-1}),$
	$\displaystyle r_{2}\,\;=\;s_{n-2}b^{n-2}+r_{3}$	$\displaystyle(0\leqq s_{n-2}<b,\quad 0\leqq r_{3}<b^{n-2}),$
	$\displaystyle\qquad\vdots$
	$\displaystyle r_{n-2}\;=\;s_{2}b^{2}+r_{n-1}$	$\displaystyle(0\leqq s_{2}<b,\quad 0\leqq r_{n-1}<b^{2}),$
	$\displaystyle r_{n-1}\;=\;s_{1}b+s_{0}$	$\displaystyle(0\leqq s_{1}<b,\quad 0\leqq s_{0}<b).$

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}<b_{i+1}$ 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