|
Basis Representation Theorem
Theorem
Let  .
For every  , there exists one and only one sequence  such that:
-
 ;
-
![\forall j \in \left[{0 \, . \, . \, k}\right]: r_j \in \N_b](/w/images/math/e/c/9/ec93d44dc552dcfb8e0206459696796a.png) ;
-
 .
This unique sequence is called the representation of n to the base b, or, informally, we can say n is (written) in base b.
Proof
Let  be the number of ways of representing n to the base b.
We need to show that  always.
Now, it is possible that some of the ri = 0 in a particular representation. So we may exclude these terms, and it won't affect the representation.
So, suppose:
where  .
Then:
from the identity  .
Note that we have already specified that b > 1.
So for each representation of n to the base b, we can find a representation of n − 1.
If n has another representation to the base b, then the same procedure will generate a new representation of n − 1. Thus  .
Note that this holds even if n has no representation at all, because if this is the case, then  .
So this inequality implies the following:
From N less than M to the N and the fact that bn has at least one representation (itself), we see:
The entries at either end of this inequality are 1, so all the intermediate entries must also be 1.
So and the theorem has been proved.
Comment
So, once we have chosen a base b > 1, we can express any positive integer n uniquely as:
Then we can write  as:
![\left[{r_m r_{m-1} \ldots r_2 r_1 r_0}\right]_b](/w/images/math/b/e/d/bedec17b22f6363ebc15e16ceb95df86.png)
| 
