Proof of the Basis Representation Theorem

According to the division algorithm, given some positive integer \(b\), any positive integer \(n\) can be represented as:

$$ n = q_0 b + a_0 $$

where \(a_0\) and \(q_0\) are unique integers and \(a_0\) is less than \(b\). Similarly, for \(q_0\):

$$ q_0 = q_1 b + a_1 $$

We keep divding by \(b\) until we reach \(q_k\) where \(q_k = 0\):

$$\begin{gather} q_1 = q_2 b + a_2 \\ q_2 = q_3 b + a_3 \\ \vdots \\ q_{k-1} = 0 * b + a_k \end{gather}$$

Note that \(q_i > q_{i+1}\).

Now replace \(q_0\) in the first equation using the second equation:

$$\begin{align} n &= (q_1 b + a_1)b + a_0 \\ &= q_1 b^2 + a_1b + a_0 \end{align}$$

Similarly, we replace \(q_1\):

$$\begin{align} n &= (q_2 b + a_2) b^2 + a_1b + a_0 \\ &= q_2 b^3 + a_2b^2 + a_1b + a_0 \end{align}$$

If we repeat this process, we get:

$$n = a_kb^k + a_{k-1} b^{k-1} + \cdots + a_3 b^3 + a_2b^2 + a_1b + a_0 $$

This proves the Basis Representation Theorem. To further establish the uniqueness, assume there is another representation using the same base:

$$n = c_kb^k + c_{k-1} b^{k-1} + \cdots + c_3 b^3 + c_2b^2 + c_1b + c_0 $$

Subtracting the first representation from the second:

$$0 = (a_k - c_k)b^k + (a_{k-1} - c_{k-1}) b^{k-1} + \cdots + (a_2-c_2)b^2 + (a_1-c_1)b + (a_0-c_0) $$

Let \(j\) be the smallest integer where \(a_j\) and \(c_j\) differ:

$$0 = (a_k - c_k)b^k + (a_{k-1} - c_{k-1}) b^{k-1} + \cdots + (a_j-c_j)b^j + \cdots + (a_2-c_2)b^2 + (a_1-c_1)b + (a_0-c_0) $$

If \(j\) is the smallest integer where \(a_j\) and \(c_j\) differ, then \(a_i - c_i = 0\) for all \(i \lt j\):

$$0 = (a_k - c_k)b^k + (a_{k-1} - c_{k-1}) b^{k-1} + \cdots + (a_j-c_j)b^j $$

Dividing both sides by \(b^j\):

$$ 0 = (a_k - c_k)b^{k-j} + (a_{k-1} - c_{k-1}) b^{k-j-1} + \cdots + (a_j-c_j)$$

Bring \(a_j-c_j\) to the other side:

$$\begin{align} -(a_j-c_j) &= (a_k - c_k)b^{k-j} + (a_{k-1} - c_{k-1}) b^{k-j-1} + \cdots + (a_{j+1}-c_{j+1})b \\ c_j-a_j &= hb \end{align}$$

This means \(c_j-a_j\) is a multiple of \(b\). Since \(0 \le c_j \lt b\) and \(0 \le a_j \lt b\), then:

$$\begin{align} -a_j \le c_j - a_j &\lt b - a_j \\ -b \lt -a_j \le c_j - a_j &\lt b - a_j \lt b \\ -b \lt c_j - a_j &\lt b \end{align}$$

If \(c_j-a_j\) is a multiple of \(b\) and \(-b \lt c_j - a_j \lt b\), then it's only possible that \(c_j - a_j=0\). This shows that \(c_j\) and \(a_j\) are equal.