Why does the division algorithm work for converting between number bases?

Question

I know and have observed that the the division algorithm can be used to convert any number in the decimal system to the binary system. However, I have tried searching for an intuition of why this method works, and I just can't seem to see anything, although I know what type of intuition I am trying to make out.

So, my question is why we can use the division algorithm to convert between the decimal bases and any other number bases?

An example from the decimal system to binary would be appreciated.

Answer 1

Choose any integer $b$ such that $b\geq 2$.

Choose some integers $d_k,d_{k-1},\ldots,d_1,d_0$, each of which satisfies $0\leq d_i<b$, and define $n$ to be $$n=d_k\cdot b^k\;+\;d_{k-1}\cdot b^{k-1}\;+\;\cdots\;+\;d_1\cdot b\;+\;d_0$$ (In other words, define $n$ to be the base-$b$ number $(d_k\ldots,d_1d_0)_b\;$.)

Recall what the division algorithm says:

Given an integer $x$ and a non-zero integer $y$, there exists a unique choice of integers $q$ and $r$ such that $x=qy+r$ and $0\leq r<y$.

Then by the division algorithm, there exists a unique choice of integers $q$ and $r$ such that $$n=q\cdot b^k+r,\qquad 0\leq r<b^k$$ Since we know that $$n=d_k\cdot b^k\;+\;\underbrace{d_{k-1}\cdot b^{k-1}\;+\;\cdots\;+\;d_1\cdot b\;+\;d_0}_{\Large0\leq\textsf{THIS} <b^k}$$ it must be that $q=d_k$ and $r=n-(d_k\cdot b^k)$. We can repeat this process, dividing by a power of $b$ and taking the remainder, dividing that remainder by the next lower power of $b$, etc., to get quotients (the numbers $q$) that are exactly the integers $d_i$ we started with, in the order $$d_k,\quad d_{k-1},\quad\ldots,\quad d_1,\quad d_0$$

What is the purpose of this? It shows that if we instead started with an integer $n$, and wanted to find out its digits when represented in base $b$, we should divide $n$ by the largest power $b^k$ for which we still have $n\geq b^k$, and then divide the successive remainders by successive powers of $b$ until we get to dividing by $b^0=1$.

---

To find the digits in the other order, we can still apply the division algorithm.

By the division algorithm, there exists a unique choice of integers $q$ and $r$ such that $$n=q\cdot b+r,\qquad 0\leq r<b$$ Since we know that $$n=\Bigl(d_k\cdot b^{k-1}\;+\;d_{k-1}\cdot b^{k-2}\;+\;\cdots\;+\;d_1\Bigr)\cdot b\;+\;d_0$$ it must be that $r=d_0$ and $q=\frac{n-d_0}{b}$. We can repeat this process, dividing by $b$ and taking the remainder, dividing the quotient by $b$ again and taking that remainder, to get remainders (the numbers $r$) that are exactly the integers $d_i$ we started with, in the order $$d_0,\quad d_1,\quad\ldots,\quad d_{k-1},\quad d_k$$

Answer 2

The best description of this process I have seen (in terms of clarity) comes from Howard Eves' Introduction to the History of Mathematics: If we have a number expressed in the ordinary scale, we may express it to base $b$ as follows. Letting $N$ be the number, we have to determine the integers $a_n,a_{n-1},\ldots,a_0$ in the expression $$ N=a_nb^n+a_{n-1}b^{n-1}+\cdots+a_2b^2+a_1b+a_0, $$ where $0\leq a_i<b$. Dividing the above equation by $b$, we have $$ \frac{N}{b} = a_nb^{n-1}+a_{n-1}b^{n-2}+\cdots+a_2b+a_1+\frac{a_0}{b}=N'+\frac{a_0}{b}. $$ That is, the remainder $a_0$ of this division is the last digit in the desired representation. Dividing $N'$ by $b$, we obtain $$ \frac{N'}{b}=a_nb^{n-2}+a_{n-1}b^{n-3}+\cdots+a_2+\frac{a_1}{b}, $$ and the remainder of this division is the next to the last digit in the desired representation. Proceeding in this way, we obtain all the digits $a_0,a_1,\ldots,a_n$. This procedure can by systematized quite conveniently, as shown below per your request of an example converting from decimal to binary.

Example: Suppose you want to convert the decimal number $197$ to binary; that is, we want to convert $(197)_{10}$ to $(?)_2$. Using the description outlined above, we keep track of the remainders until the process or algorithm terminates:

• Remainders: $1,0,1,0,0,0,1,1$

We now use these remainders to make the desired base conversion (take note of how the remainders are "read in from back to front"): $$ (197)_{10}=1(2^7)+1(2^6)+1(2^2)+1=(11000101)_2 $$

Answer 3

Because the base $b$ representation of a number is "invertible". Let a number be

$$n=\sum_{i=0}^dd_ib^i,$$

where $b$ is the base and the $d_i$ are the digits, such that $0\le d_i<b$.

For example, $$443_5=4\cdot5^2+4\cdot 5+3=123.$$

By the remainder theorem, there is a unique quotient $q$ and a unique remainder $r$ such that

$$n=qb+r\text{, and }0\le r< b.$$

Like $$123=24\cdot5+3\text{, and }0\le3<5.$$

Obviously the initial equation can be written as

$$n=\left(\sum_{i=0}^{d-1}d_{i+1}b^i\right)b+d_0,$$ so that the remainder is the last digit and the quotient is the initial number with the last digit dropped.

As you can check, $$\color{green}{443}_5=123=24\cdot5+3=\color{green}{44}_5\cdot5+\color{green}{3}.$$

Iterating,

$$\color{green}{44}_5=24=4\cdot5+4=\color{green}{4}_5\cdot5+\color{green}{4}.$$