# What's the intuition for why repeated div and mod converts a number to another base?

This guide here tells how to base 10 number to binary. For example, for the first bit, you take $356_{10} \div 2 = 178 \, R \, 0$.

Because the remainder was 0, the first bit is $0$ and we recurse this procedure on $178$.

I would like to be able to explain why this works (why it returns the bits in least significant order)? Why should I believe the resulting bits are actually the number in base 2?

• Try proving to yourself that this method works for converting base $10$ to base $10$. That might help you "get it". – Callus - Reinstate Monica Sep 2 '14 at 1:45

Convert $20$ from base $10$ to base $2$

If it helps think of this example as counting $20$ apples in base $2$ system

Step 1 : Count how many $2$-apple groups are there
$\color{red}{20 = 2\times 10 + }\color{green}{0}$
This division tells us that the number of $2$-apple groups is $10$ and $1$-apple groups is $0$

Step 2 : Count how many $4$-apple groups are there
$\color{red}{10 = 2\times 5+ }\color{green}{0}$
This division tells us that the number of $4$-apple groups is $5$, $2$-apple groups is $0$ and $1$-apple groups is $0$

Step 3 : Count how many $8$-apple groups are there
$\color{red}{5 = 2\times 2 + }\color{green}{1}$
This division tells us that the number of $8$-apple groups is $2$, $4$-apple groups is $1$, $2$-apple groups is $0$ and $1$-apple groups is $0$

Step 4 : Count how many $16$-apple groups are there
$\color{red}{2 = 2\times 1 +}\color{green}{0}$
This division tells us that the number of $16$-apple groups is $1$, $8$-apple groups is $0$, $4$-apple groups is $1$, $2$-apple groups is $0$ and $1$-apple groups is $0$

Step 5 : Count how many $32$-apple groups are there
$\color{red}{1 = 2\times 0 + }\color{green}{1}$
This division tells us that the number of $32$-apple groups is $0$, $16$-apple groups is $1$, $8$-apple groups is $0$, $4$-apple groups is $1$, $2$-apple groups is $0$ and $1$-apple groups is $0$

Overall : $$\left(20\right)_{10} = \left(\color{green}{10100}\right)_{2}$$

As you can see, changing base is like changing the size by which you group things. I hope you might be having some idea about the place value!

It employs the division algorithm to unwind the radix $\,b\,$ representation of $\,n = n_0,\,$ i.e.

$\qquad\qquad\qquad \qquad\, n_0 = d_0 + d_1 b + \cdots + d_k b^k\quad\ \Rightarrow\ d_0 =\, n_0\, {\rm mod}\ b$

$\qquad n_1 := (n_0\!-d_0)/b = d_1 + d_2 b + \cdots + d_k b^{k-1}\,\Rightarrow\ d_1 =\, n_1\ {\rm mod}\ b$

$\qquad n_2 := (n_1\!-d_1)/b = d_2 + d_3 b + \cdots + d_k b^{k-2}\,\Rightarrow\ d_2 =\, n_2\ {\rm mod}\ b$

$\qquad\ \vdots\qquad\qquad\vdots\qquad\qquad\quad \qquad\qquad \vdots\qquad\qquad\qquad\qquad\quad\vdots$

• The vertical dots present a very confusing pattern, but maybe that's just the mobile representation... – abiessu Sep 2 '14 at 3:22

$$\begin{array}{ccl} 356&=&2\cdot 178\\ &=&4\cdot 89\\ &=& 4+4\cdot 88\\ &=& 4+8\cdot44\\ &=& 4+16\cdot 22\\ &=& 4+32\cdot 11\\ &=&4+32+32\cdot10\\ &=&4+32+64\cdot5\\ &=&4+32+64+64\cdot 4\\ &=&4+32+64+128\cdot 2\\ &=&4+32+64+256 \end{array}$$ And that is essentially the base 2 representation of 356.

For your example, the first division simply says that $356 = 178\cdot 2 + 0$, so that the low-order bit of $356_2$ must be zero. Then $178$ is the decimal representation of all bits but the low-order bit of $178$. Proceed by induction.

• Off-by-one error with the $357$? – abiessu Sep 2 '14 at 3:20