Prove that there is only one unique base b representation of any natural number.

I have been asked to prove that for any integer base $b \geqslant 2$, every natural number has a unique base $b$ representation. I am not sure if this has been answered somewhere already, but I could not find a general answer that can be applied to any base.

Would the division algorithm apply here? I know that it would serve to give every number a unique quotient and remainder, but I'm not sure how exactly to craft the proof. I appreciate any input, thanks in advance!!

Solution 1:

Let $N$ be a natural number. You want to write it as $$ N = a_{0} + a_{1} b + a_{2} b^{2} + \dots + a_{k} b^{k} $$ for a suitable $k$, and $0 \le a_{i} < b$.

Now rewrite the above as $$ \begin{cases} N = a_{0} + q b,\\ 0 \le a_{0} < b \end{cases}$$ to see that $a_{0}$ is uniquely determined as the remainder of the division of $N$ by $b$.

Now consider $$ q = a_{1} + a_{2} b + \dots + a_{k} b^{k-1} $$ and repeat, that is, use induction.

Solution 2:

Below we show that uniqueness of radix rep is a special case of the Rational Root Test.

If $\,g(x) = \sum g_i x^i$ is a polynomial with integer coefficients $\,g_i\,$ such that $\,0\le g_i < b\,$ and $\,g(b) = n\,$ then we call $\,(g,b)\,$ a radix $\,b\,$ representation of $\,n.\,$ It is unique: $ $ if $\,n\,$ has another rep $\,(h,b),\,$ with $\,g(x) \ne h(x),\,$ then $\,f(x)= g(x)-h(x)\ne 0\,$ has root $\,b\,$ but all coefficients $\,\color{#c00}{|f_i| < b},\,$ contra the below slight generalization of: $ $ integer roots of integer polynomials $\,f(x)\in\Bbb Z[x]\,$ divide its constant term $\,f(0)\,$ [an obvious special case of the Rational Root Test].

Theorem $\ $ If $\,f(x) = x^k(\color{#0a0}{f_0}\!+f_1 x +\cdots + f_n x^n)=x^k\bar f(x)\,$ is a polynomial with integer coefficients $\,f_i\,$ and with $\,\color{#0a0}{f_0\ne 0}\,$ then an integer root $\,b\ne 0\,$ satisfies $\,b\mid f_0,\,$ so $\,\color{#c00}{|b| \le |f_0|}$

Proof $\ \ 0 = f(b) = b^k \bar f(b)\,\overset{\large b\,\ne\, 0}\Rightarrow\, 0 = \bar f(b),\,$ so, subtracting $\,f_0$ from both sides yields $$-f_0 =\, b\,(f_1\!+f_2 b+\,\cdots+f_n b^{n-1})\, \Rightarrow\,b\mid f_0 \underset{\large \color{#0a0}{f_0\,\ne\, 0}}\Longrightarrow\, |b| \le |f_0|\qquad {\bf QED}\qquad\quad$$

Solution 3:

Let two representations of a number be such that they differ in the $k^{th}$ digit ($k$ zero-based, from the right).

Then

$$(n\text{ div } b^k)\bmod b$$

has different values for these two representation, which is contradictory ($\text{div}$ denotes integer division).

Solution 4:

The OP asked

Would the division algorithm apply here?

Here we provide, working in the natural numbers $\Bbb N =\{0,1,2,\dots\}$, a proof of uniqueness that doesn't use full blown Euclidean division; we only need the following weaker result.

Lemma 1: Let $b,k,h,r \in \Bbb N$ satisfy

$$\tag 1 kb = hb + r \; \text{ with } r \lt b$$

Then $k = h$ and $r = 0$.
Proof
If $k \lt h$ then $kb \lt hb \le hb + r$, so $\text{(1)}$ is false.
If $k \ge h$ then write $k = h + u$ with $u \ge 0$. Substituting into $\text{(1)}$,

$$ kb = (h + u)b = hb + ub = hb + r $$

so it must be true that $ub = r$. If $u \ge 1$, $\; ub \ge b$ and that can't happen since $r \lt b$. So $u = 0$ and $k = h$, and substituting into $\text{(1)}$,

$$\quad hb = hb + r $$

and so $r = 0$. $\quad \blacksquare$

Note: You can use an alternate proof for lemma 1: If both $k$ and $h$ are greater than $0$ they both have a predecessor, and lemma 1 is equivalent to the statement obtained by replacing both both $k$ and $h$ with these smaller numbers. So there is a 'truth chain' allowing us to assume that $k=0$ or $h=0$.
If $k = 0$ both $h$ and $r$ must be $0$.
If $h = 0$ then we have $r = kb$. If $k \ge 1$ then $r \ge b$ but that can't happen since $r$ is assumed to be less than $b$. So $k = h = r = 0$.

Let $b \ge 2$.

Theorem 2: Let a number $n \ge 0$ have two $\text{Base-b}$ representations $x$ and $y$. Then, using Capital sigma notation with $0\text{-padding}$ if necessary, we can express the equality of these two representations by writing

$$ \tag 2 \sum_{i=0}^k x_i b^i = \sum_{i=0}^k y_i b^i \; \text{ with the coefficients } x_i \text{ and } y_i \text{ all between } 0 \text{ and } b-1$$

Then if $j \in \{i \, | \, 0 \le i \le k\}$, $\;x_j = y_j$, i.e. the coefficients are all equal.
Proof
If the two families $(x_i)$ and $(y_i)$ are not identical, let $j$ be the first integer where $x_j \ne y_j$. Cancelling the initial (if any) equal terms from both sides of equation $\text{(2)}$, there would remain

$$ \tag 3 \sum_{i=j}^k x_i b^i = \sum_{i=j}^k y_i b^i $$

Assume that $x_j \gt y_j$ with $x_j = y_j + u$. Cancelling the $y_jb^j$ term from each side of $\text{(3)}$ allows us to write

$$ \tag 4 ub^j + \sum_{i={j+1}}^k x_i b^i = \sum_{i={j+1}}^k y_i b^i \text{ with } 0 \lt u \lt b$$

since it must be true that $k \ge j+1$. But then, by factoring out $b^j$ and using algebra, we can write

$$ \tag 5 u + kb = hb$$

for some numbers $k$ and $h$. Since $u \lt b$, applying lemma 1 we must conclude that $u = 0$. But that can't happen since we assumed that $x_j \ne x_j$.

The reductio ad absurdum argument is constructed in a like manner when $y_j \gt x_j$.

So assuming that $x_j \ne y_j$ leads to a contradiction.$\quad \blacksquare$

BONUS MATERIAL

We can also prove the existence of $\text{Base-b}$ representations without using Euclidean division (see this). It is an easy exercise to show that the existence of $\text{Base-b}$ representations can be used to demonstrate the existence part of the Euclidean division theorem.

Exercise: Prove the uniqueness part of the Euclidean division theorem using lemma 1.
Hint: Use the same technique used in theorem 2, taking the difference $u$ between two numbers,