|
Theorem. Let the positive integer $b$ be the base of a positional digital system. Every positive integer $a$ may be represented uniquely in the form
 |
(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 decimal 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
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 representation $$a \;=\; t_mb^m+t_{m-1}b^{m-1}+\ldots+t_1b+t_0$$ with $0 \leqq t_i \leqq s\!-\!1$ , $b_m \neq 0$ . The equality
 |
(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_1b \equiv t_1b \pmod {b^2}$ , whence $s_1 \equiv t_1 \pmod b$ , and as before, $t_1 = s_1$ . We may continue in similar manner and see that always $t_i = s_i$ , whence also $m = n$ . Accordingly, the both representations 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_ib_1b_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.
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png)
