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

Question

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?

Answer 1

Maybe consider a simpler example to start with :

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!

Answer 2

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

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

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

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

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

i.e. unwind the nested Horner form $\,d_0 + b(d_1 + b (d_2 + \cdots b(d_k)\cdots))$ operations that are used to build up radix representation - by repeated divisions by $\,b\,$ (with remainder).

Answer 3

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.

Answer 4

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