Uniqueness of radix representation of integers in base 3

I have recently begun self-studying Number Theory, and am working on proving:

Show that every integer $n>0$ can be uniquely written as $$n = \sum_{i=0}^mc_i3^i$$ where $c_i \in \{ -1,0,1\}$ and $c_m \neq 0$.

I believe I have already shown the existence portion of this proof correctly, and now I am looking for some hints on the uniqueness part. So far what I have tried is:

Suppose for the sake of contradiction that there is an alternate representation of $n$ besides $n = \sum_{i=0}^mc_i3^i$, say $n = \sum_{i=0}^pb_i3^i$ where we still have $b_p \neq 0$ and $b_i \in \{-1,0,1\}$.

At this point I felt that I first need to establish that $m=p$, and second show $c_i=b_i$ for each $i \in \{1,2,\dots, m\}$. To show the former, I left off in my proof by contradiction with

Without loss of generality suppose $p>m$. We know there is an integer $q$ such that $m+q=p$. We have two ways of writing $n$, which means $$\sum_{i=0}^pb_i3^i-\sum_{i=0}^mc_i3^i=0 \\ \implies \left(\sum_{i=0}^mb_i3^i+\sum_{i=m+1}^{m+q}b_i3^i\right)-\sum_{i=0}^mc_i3^i=0 \\ \implies \sum_{i=0}^m(b_i-c_i)3^i+\sum_{i=m+1}^{m+q}b_i3^i=0 \\ \implies \sum_{i=m+1}^{m+q}b_i3^i=\sum_{i=0}^m(c_i-b_i)3^i$$

At this point I am stuck. If anyone has any hints to help me find the contradiction or feel that there is a better way to establish uniqueness, please let me know!

• Suppose $b_{m+1} = 1$. Then even if all the $c_i - b_i = 1$, maximizing the expression on the right, then that sum would still be less than $3^{m+1}$. There is a similar case for $b_{m+1} = -1$. For the case $b_{m+1} = 0$, there must be some $b_j \neq 0$, $j > m+1$. Jan 5, 2015 at 16:09
• Note that that's called "balanced ternary," whereas just "ternary" usually means base $3$ with the digits $0$, $1$, $2$. Thus, in ternary, $26$ is $222$ but in balanced ternary you'd have a $1$ followed by two $0$s and ending with a $-1$.
– user153918
Jan 5, 2015 at 18:26

If you know a bit about modular arithmetic, then there is a relatively easy way to work this out (it is equivalent to the proofs already here, but perhaps is a little cleaner conceptually). Suppose that you have $x_0 = \sum_{n = 0}^\infty a_n 3^n = \sum_{n = 0}^\infty b_n 3^n$ (with the understanding that for large enough $n$, $a_n$ and $b_n$ are $0$).

Take $x_0$ modulo $3$. It is apparent that we must have $x_0 = a_0 = b_0 \mod 3$, which of course implies that $a_0 = b_0$. Now, consider $x_1:=\frac{x_0 - a_0}{3}$. It is an integer, so it makes sense to reduce it modulo $3$ again---this time, we get the equality $x_1 = a_1 = b_1 \mod 3$, so $a_1 = b_1$. Define $x_2 := \frac{x_1 - a_1}{3}$, rinse, and repeat. An easy induction proves the result.

• Thanks for breaking it down a bit more! That should help me get it all finished up :) Jan 6, 2015 at 2:51

The best approach is to use induction.

If $\sum a_i3^i = \sum b_i3^i$, first show that $a_0=b_0$ and thus that:$$\sum_{i>0} a_i3^{i-1} = \sum_{i>0} b_i3^{i-1}$$ Then apply the induction hypothesis.

• Thank you, I will give this a shot. Why did you subtract $1$ from $i$ in the exponent after showing $a_0=b_0$? Jan 5, 2015 at 16:28
• The claim you are proving by induction considers sums which range from terms starting with $3^0$. Jan 6, 2015 at 2:14

Hint $$\$$ Viewing radix representation as a polynomial in the radix, this can be reduced to a result related to the rational root test - see the result below, which, slightly modified, also works here.

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$$

Hint:

• Note that $$(3^m+3^{m-1}+\ldots+1)-(-3^m-3^{m-1}-\ldots-1)=3^{m+1}-1$$ since $3-1=2$ and $3^{m+1}-1=3\cdot3^m-1=2\cdot3^m+(3^m-1)$.
• You could strengthen your argument so that each integer from $(-3^m-\ldots-1)$ to $(3^m+\ldots+1)$ can be expressed.
• In such case you are representing $3^{m+1}$ possibilities with at most $3^{m+1}$ different sums, that is, you get uniqueness for almost free.
• The first bullet makes for an elegant induction hypothesis, because $$3^{m+1}+(-3^m-3^{m-1}-\ldots-1) = (3^m+3^{m-1}+\ldots+1)+1.$$

I hope this helps $\ddot\smile$

• @graydad That was a typo, updated now. Jan 5, 2015 at 16:47
• I'm still unsure how you get the first equality. Is it $$(3^{m+1}+3^{m}+\ldots+3^1)-(-3^m-3^{m-1}-\ldots-3^1-1)=3^{m+1}-1$$ Jan 5, 2015 at 16:48
• @graydad After simplifying you get $2\cdot 3^m+2\cdot3^{m-1}+\ldots+2 = 3^{m+1}-1$, which is intuitively true because it is the highest $m$-digit number you can get in the ordinary base-3, i.e. $22222\ldots222_\text{base 3}$. Jan 5, 2015 at 16:56
• Ah I see it now. Thank you for explaining further. I will play around with this result :) Jan 5, 2015 at 17:06

Outline of Proof: 1) first assume n has a representation as required

2) Show that for each representation of $n$ we can find a representation for $n-1$. This means if we know a representation for an integer greater than $n$, we can find one for $n$.

3)$3^n$ is greater than n and has a representation; therefore so does $n$

4)Squeeze the number of representations for $n$ between 1 and 1.

Suppose that n has a representation of the form $n = \sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+c_03^0$. Now we want to subtract 1 from both sides, $n-1 = \sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+c_03^0-1$. Now, $n-1$ does not have the proper representation yet. On its own $-1$ can be written $-1=-1*3^0$. We can now write $n-1 = \sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+(c_0-1)3^0$.

We want to say here that given a representation of $n$ satisfying the requirements we can find a representation of $n-1$ that does as well, but for the case $c_0=-1$ we get a coefficient of $-2$ for the last term.

So for the case $c_0=-1$ we will use the formula $-2*3^j=-3^{j+1}+3^j$ to rewrite $n-1$.$n-1 = \sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+(c_0-1)3^0=c_m3^m+c_{m-1}3^{m-1}+...-2*3^0=c_m3^m+c_{m-1}3^{m-1}+...-3^1+3^0$. Now we realize that there may exist a term w/ coefficient $-1$ and exponent $1$ and we are back where we started.

But, there must exist a last term with $-1$ as a coefficient. Let the kth term be the last one with coefficient $-1$, then we have $n-1=c_m3^m+c_{m-1}3^{m-1}+...-3^{k+1}+3^k+3^{k-1}+...+3^0$ and this representation meets the requirements.

So we have shown that for each representation of $n$ we can find a representation for $n-1$. Since $3^n>n>0$ and $3^n$ has a representation(itself) then a representation for n can be found progressively.

Uniqueness:

Let $b_k(n)$ represent the total number of representations for $n$. Since for each representation of $n$ we can find one for $n-1$ we have $b_k(n)$<=$b_k(n-1)$. (Skipping a bit) we have finally 1<=$b_k(3^n)<=b_k(n)<=b_k(1)=1$. The total number of representations for $n$ is between $1$ and $1$ and must therefore be $1$