# Why can we convert a base $9$ number to a base $3$ number by simply converting each base $9$ digit into two base $3$ digits?

Why can we convert a base $9$ number to a base $3$ number by simply converting each base $9$ digit into two base $3$ digits ?

For example $813_9$ can be converted directly to base $3$ by noting

\begin{array} \space 8_9&=22_3 \\ \space 1_9 &=01_3 \\ \space 3_9 &=10_3 \\ \end{array}

Putting the base digits together ,we get $$813_9=220110_3$$

I know it has to do with the fact that $9=3^2$ but I am not able to understand this all by this simple fact...

• This is actually useful (but not with $9$ and $3$). We can very cheaply go back and forth between hexadecimal (base $16$) and binary. – André Nicolas Jan 26 '16 at 8:30
• This also applies to converting between: binary, octal, hexadecimal systems – Max Payne Jan 26 '16 at 8:31

Consider $N$ in base 3. For simplicity, we can assume that $N_3$ has an even number of digits: if it doesn't, just tack on a leftmost $0$. So let: $$N_3 = t_{2n+1} t_{2n}\dotsc t_{2k+1} t_{2k} \dotsc t_1 t_0.$$ What this positional notation really means is that: $$N = \sum_{i = 0}^{2n+1} t_i 3^i,$$ which we can rewrite as: \begin{align} N &= \sum_{k = 0}^{n} (t_{2k+1} 3^{2k+1} + t_{2k} 3^{2k}) \\ &= \sum_{k = 0}^{n} (3 t_{2k+1} + t_{2k}) 3^{2k} \\ &= \sum_{k = 0}^{n} (3 t_{2k+1} + t_{2k}) 9^{k}. \\ \end{align}

But now, note that for each $k$, $3 t_{2k+1} + t_{2k}$ is precisely the base-9 digit corresponding to the consecutive pair of base-3 digits $t_{2k+1} t_{2k}$.

• Altough I've already accepted an answer,I thought to let you know that this answer has been so insightful.Thanks for your time ! – Mr. Y Jan 26 '16 at 9:18
• How nice — thank you:) and you're welcome. – BrianO Jan 26 '16 at 9:24
• That is the real good prove – JnxF Jan 26 '16 at 9:57
• Oh my - thanks doubly. – BrianO Jan 26 '16 at 10:05
• yes this is the proof. My answer is just a visual. +1 – Max Payne Jan 26 '16 at 10:16

This has more to do with place value.

Consider the image: The key is the fact that $3^2 = 9$

• All the value below $3^2$ ($3^0$ and $3^1$) has to be accomodated in $9^0$

that is

• all the values in $9^0$ have to be accommodated in the two places below $3^2$ ($3^0$ and $3^1$)

Similarly for any other places.

• This rule also applies to conversion between binary and octal, or binary and hexadecimal, or conversion between any base $k$ and base $k^n$

In general, for conversion of a number $N$ in any base $k$ to base $k^n$, each digit of $N_{k^n}$ get converted to n digits of $N_k$

• Thanks for the answer .One question : in general if we have that some number $c$ (I am considering everything in base $10$) such that $c=b^n$ does this mean that I can convert the number $c$ in base $b$ by simple converting each base $10$ digit of $c$ into $n$ base $b$ digits ?Or is this something that works only for these special cases ? – Mr. Y Jan 26 '16 at 8:56
• @Mr.Y, yes, you can. An even stronger statement would be: given $a^n=b^m$, we could convert a base $a^n$ number, say, $k$, to base $b^m$, by converting every $n$ digits of $k$ (base $a^n$) to $m$ digits base $b^m$. – vrugtehagel Jan 26 '16 at 9:02

I'm not sure whether you're asking for a proof, or some intuition. The proof is fairly mechanical, so I'll explain why you might expect this to be true.

Putting your information theory hat on, two base 3 digits carry exactly as much information as one base 9 digit. That is, suppose you know I'm going to pass you two digits, each from 0,1 and 2. Then you know there are $3 \cdot 3 =9$ possibilities for what information I could pass.

On the other hand, if I passed you a single digit from 0,1,...,8, then there are again 9 possibilities.

Continuing in this fashion, $n$ digits of base 9 pass as much information as $2n$ digits of base 3.

This isn't exactly a proof yet. You'd need to prove that you don't skip any values. Perhaps doing the computation you describe can never return the value $102_3$. Thankfully it can. But you'd need to think about why this will always work.

Let's look at what you base $9$ number actually means. $$813_9=8\cdot 9^2+1\cdot 9^1+3\cdot 9^0$$ If we wish to write this as powers of $3$ with coefficients between $0$ and $2$, we can simply do \begin{align} 3\cdot 9^0&=1\cdot 3^1+0\cdot 3^0\\ 1\cdot 9^1&=0\cdot 3^3+1\cdot 3^2\\ 8\cdot 9^2&=2\cdot 3^5+2\cdot 3^4\\ \end{align}

Why can we do this?

Why can we write $$a_n\cdot 9^n=b_{2n+1}\cdot 3^{2n+1}+b_{2n}\cdot3^{2n}$$ First note that $9^n3^2n$, so when dividing the equation by that, we get $$\frac{a_n\cdot 9^n}{3^{2n}}=a_n=3b_{2n+1}+b_{2n}=\frac{b_{2n+1}\cdot 3^{2n+1}+b_{2n}\cdot3^{2n}}{3^2n}$$ So actually, the problem comes down to writing a number $0\leq a_n<9$ as $3b_{2n+1}+b_{2n}$, where $0\leq b_{2n},b{2n+1}<3$. This is obviously possible.

Why does this work for binary and hexadecimal?

Actually, the answer is fairly similar. The problem can be reduced equivalently, resulting in the equation $$a_n=8a_{4n+3}+4a_{4n+2}+2a_{4n+1}+a_{4n}$$ Where $0\leq a_n<16$ and $0\leq a_{2n+3},a_{2n+2},a_{2n+1},a_{2n}<2$. The solvability of this equation is in my opinion a little less obvious, but still quite understandable; But, for the sake of a more thourough understanding, we could look at hexadecimal-octagonal conversion. This comes down to the easy equation $a_n=2b_{2n+1}+b_{2n}$, where $0\leq a_n<16$ and $0\leq b_{2n+1},b_{2n}<8$. This is cleary solvable. Doing this for octagonal-base 4 conversion and base 4-binary conversion shows with a recurrance-like approach that this indeed works for hexadecimal-binary conversion.

Hope this helped!

Hint:

$$\color{blue}1\cdot3^5+\color{blue}0\cdot3^4+\color{green}2\cdot3^3+\color{green}2\cdot3^2+\color{red}0\cdot3^1+\color{red}1\cdot3^0 =(\color{blue}1\cdot3^1+\color{blue}0)3^4+(\color{green}2\cdot3^1+\color{green}2)3^2+(\color{red}0\cdot3^1+\color{red}1)3^0\\ =\color{blue}3\cdot9^2+\color{green}8\cdot9^1+\color{red}1\cdot9^0$$

$$\color{blue}{10}\color{green}{22}\color{red}{01}_3=[\color{blue}{10_3}|\color{green}{22_3}|\color{red}{01_3}]_9=\color{blue}3\color{green}8\color{red}1_9$$