1

Problem: Prove that any positive integer $a$ can be uniquely expressed in the form $a=3^m+b_{m-1}3^{m-1}+...b_0$, where each $b_j=0,1,\text{ or }-1$.

My Attempt: First we will prove that any positive integer $a$ has a unique representation in base $3$. Say, $$a=\sum_{i=0}^{n}x_i3^i, \text{where }x_i\in \{0,1,2\}$$ Then suppose to the contrary, we have another representation of the integer $a$ implying that $$\sum_{i=0}^{n}x_i3^i=\sum_{i=0}^{n}k_i3^i\Rightarrow \sum_{i=0}^{n}(x_i-k_i)3^i=0.$$ Now since all the coefficients in the representaion of the integer $0$ are $0$ we can conclude that $x_i=k_i$ for all $0\leq i\leq m-1$ which is a contradiction. Hence all positive integers have unique representation in base $3$. Now if we replace $2*3^{k}=3^{k+1}-3^k$ for all terms having a coefficient of $2$ we get a representation of $a$ which is of the form $\sum x_k3^k$ ,where $x_k\in \{-1,0,1\}$. And since the representation of a number in base $3$ is unique we can say that this representation is also unique since it is derived from it.

I would like to know whether my proof is correct or not. Note that this question is different from all other questions in that it asks only for proof verification and not for any hints or solutions of this problem

Student
  • 9,196
  • 8
  • 35
  • 81

1 Answers1

1

The proof is incorrect because as pointed out I have not shown that $0$ has a unique representation. A way of solving this problem is as follows: Suppose that $a$ is the least positive integer that admits non-unique representation. Then we have, $$a=\sum_{i=0}^{h}x_i3^i=\sum_{i=0}^{k}y_i3^i.$$ This expression can be written as $$a=x_0+3\left(\sum_{i=1}^{h}x_i3^{i-1}\right)=y_0+3\left(\sum_{i=1}^{k}x_i3^{i-1}\right).$$ By the uniqueness of remainder under division by $3$, we can say that $x_0=y_0.$ Set $M$ as $$M=\left(\sum_{i=1}^{h}x_i3^{i-1}\right)=\left(\sum_{i=1}^{k}y_i3^{i-1}\right).$$ Since $M<a$ we conclude that $x_i=y_i$ and $h=k$ as we assumed that $a$ was least positive integer that admits a non-unique representation. Thus $a$ has a unique representation. After this step the remainder of the proof is correct.

Student
  • 9,196
  • 8
  • 35
  • 81
  • Instead of appealing to "uniqueness of remainder" I would include the details on how this is used. One simple way is using induction. If $0 = \sum_{i=0}^n a_i 3^i$ with $a_i\in{-2,-1,0,1,2}$ then $a_0 = -3a_1 - 9a_2 - \ldots - a_n 3^n$ so $3\mid a_0$ forcing $a_0 = 0$. Now assume for induction that $a_0=a_1=\ldots=a_k = 0$ then $a_{k+1} = -3a_{k+2} - 9a_{k+3} - \ldots - 3^{n-k-1}a_n$ so $3\mid a_{k+1} \implies a_{k+1} = 0$. By induction $a_i \equiv 0$ for all $i$. – Winther Nov 03 '16 at 16:06