Why the remainders of the division of a number by 2 results in the number in binary?

Question

For example 14, if you divide be 2 it equals 7 and the remainder = 0, then 7/2 = 3 with r = 1 then 3/2 = 1 and r = 1 then 1/2 = 0 with r = 1. If we take the r's and put them togheter 1110 is 14 in binary. I don't understand the intuition behind this, why does this work?

Answer 1

We can write any natural number $n$ as a sum of powers of $2$:

$$n = b_k 2^k + b_{k-1} 2^{k-1} + \cdots + b_{0} 2^0$$

where each $b_i, 0 \leq i \leq k$ is $0$ or $1$.

When we divide $n$ by $2$, we therefore see that the remainder is $b_0$. The result of the integer division is $b_k 2^k + b_{k-1} 2^{k-1} + \cdots + b_{1} 2^1$. Dividing again by $2$, we see in the same way as before that the remainder is $b_1$. This line of reasoning can be carried out for every subsequent division; the remainder of the $j$th successive division is $b_j$.

Answer 2

It should be clear that the remainder after the first division by $2$ finds the lowest digit - $0$ or $1$ depending on whether the number is even or odd.

Then think about how you might find the next lowest digit. That's like the ten's place in ordinary notation. If you have $1574$ that $7$ is what you get if you subtract the $4$, divide by $10$ (cancel the zero, move the decimal point one place left) and look at the new units digit.

So for binary, subtract the units digit ($0$ or $1$, whichever it happened to be) and divide by $2$ to shift left.

Keep going as long as you need to.

Answer 3

This is because of Horner's scheme for evaluating polynomials: \begin{align}&a_nx^n+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}\dots+a_1x+a_0\\ ={}(\dots(((&a_nx+a_{n-1})x+a_{n-2})x+\dots+a_1)x+a_0. \end{align} The successive divisions by $2$ yield \begin{align} 14&=7\cdot 2+0\\&=(3\cdot2+1)\cdot 2+0=3\cdot2^2+1\cdot 2+0\\ &=\color{red}{((1\cdot2+1)\cdot2+1)\cdot 2+0}=(1\cdot2+1)\cdot2^2+1\cdot 2+0 \\ &=1\cdot2^3+1\cdot2^2+1\cdot 2+0 \end{align}

Answer 4

Might as well do it for an integral base $b>1$ instead of $2$.

For every integer $n\ge 0$ take the largest integer $q$ so that $b q \le n$. Clearly $q \ge 0$, and $n - q b \ge 0$. Since $(q+1)b >n$, we have $n - q b < (q+1)b- q b = b$. Therefore, $n - q b \in \{0,1,\ldots, b-1\}$. This is the division with remainder. For every integer $n\ge 0$ there exists integers $q\ge 0$ and $r \in \{0,1,\ldots, b-1\}$ so that $$n = q b+ r$$ $b$ and $r$ with these properties are unique. $b$ is the quotient, and $r$ is the remainder of the division of $n$ by $b$.Note that $$0 \le q \le \frac{n}{b}$$

Take now an integer $n\ge 0$, denote $q_0=n$, and do successive divisions

$$q_0 = q_1 b + r_0 \\ q_1 = q_2 b + r_1\\ q_2= q_3 b + r_2 \\ \ldots \ldots\\ q_{k-1} = q_k b + r_{k-1}\\ q_k = q_{k+1} b + r_k$$

Since $0\le q_{k+1} \le \frac{q_k}{2}$, there exists a smallest $k\ge 0$ so that $q_{k+1} = 0$. From the above equalities we get $$q_k = r_k \\ q_{k-1} = r_k b + r_{k-1}\\ q_{k-2}=(r_k b+r_{k-1})b + r_{k-2}= r_k b^2 + r_{k-1} b+ r_{k-2}\\ \ldots \ldots\\ q_0 = (r_k b^{k-1}+ r_{k-1} b^{k-2} + \cdots + r_2 b + r_1) b + r_0 = \\ =r_k b^k + r_{k-1} b^{k-1} + \cdots + r_1 b + r_0$$