On the proof of existence and uniqueness of radix representation

Base-b Representation of an Integer: Why can I make the assumption about number of terms in expansions in uniqueness part?

Reading the book of Koshy I have come across the below theorem. It states that I can write any integer $N$ in a base $b\ge2$ representation $N=a_kb^k+...+a_1b+a_0$ such that $0\le a_i<b$, $a_k \neq 0$ for some $k\ge0$.

In the uniqueness part, why can I assume the expansions contains the same number of terms ? I must prove that all expansions of $N$ equal the one in the theorem, but if I add terms to the expansion by zero coefficients, well, then the expansion is not in the proper form anymore ? (the greatest term in the expansion is $0$ if I add zero coefficients) .

Can someone help clear this out ?

Why can I assume the expansions contain the same number of terms ? If I add terms to the expansion, well then I've violated the form of the expansion ?

Solution 1:

Appending the leading zeros is a notational convenience that permits one to write uniformly the coefficients in the subtraction. This can prove confusing, as you note. However, it is not needed since the proof can be presented more clearly as follows.

The idea behind the proof is that radix $\,b\,$ representation arises by iterating the operation of division by $\,b\,$ (with remainder). Since the quotient and remainder in the division algorithm are unique, this implies the uniqueness of the digits (remainder sequence) in radix representation. One can prove this by induction using the recursive definition of the radix representation. Alternatively one can prove it more directly as follows.

Suppose that $\,n\,$ has two different radix reps. Let $\,k\,$ be the least place (digit index) where the differ. Then, dividing both reps by $\,b^k\,$ yields $\ q b^k + r = n = q' b^k + r'.\ $ Note $\,r' = r\,$ since all digits of index $< k$ are equal, so subtracting $\,r = r'$ yields $\, q b^k = q' b^k.\,$ Cancelling $\,b^k\ne 0\,$ yields $\,q = q'.$ Thus $\,q\,$ and $\,q',\,$ being equal, have equal remainder when divided by $\,b,\,$ by the uniqueness of the remainder. But these remainders are the $k$'th digit of each rep which, by hypothesis, differ, a contradiction.

To formalize the proof in your book we can use polynomials as follows. 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)\,$ the 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 following slight generalization of: $ $ integer roots of integer polynomials divide their constant term.

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\, \overset{\large \color{#0a0}{f_0\,\ne\, 0}}\Rightarrow\, |b| \le |f_0|\qquad {\bf QED}\qquad\quad$$