14
$\begingroup$

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.

$\endgroup$

3 Answers 3

9
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I understand everything you said, however, this is not the method I have in my textbook. My textbook tells me just to divide by $2$ rather than by a power of 2, and then divide the quotient of that division by 2 Et Cetera. And, it tells me that the remainders are the digits of the integer in base 2 where they aread from down to up. Can you perhaps edit to include this? $\endgroup$ Commented Jul 13, 2015 at 20:31
  • 1
    $\begingroup$ @ReinhildVanRosenú: Excellent point, I hadn't thought to include the other direction. I've added a section to my answer about this, please let me know if I can clarify anything. $\endgroup$ Commented Jul 13, 2015 at 20:37
  • $\begingroup$ Sorry, but I just looked at Daniel's answer and I think his answer includes the other direction. $\endgroup$ Commented Jul 13, 2015 at 20:41
  • $\begingroup$ But, I think your answer with new edit is much more succinct and direct. :) $\endgroup$ Commented Jul 13, 2015 at 20:44
8
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Very good answer, totally cleared my mind! $\endgroup$ Commented Dec 4, 2022 at 9:48
  • $\begingroup$ This answer is fantastic, and gave me absolute clarity on this question. Nice work $\endgroup$ Commented Oct 29, 2023 at 16:24
3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .