0
$\begingroup$

This question already has an answer here:

I am having a hard time understanding why the division algorithm works during base conversion even after reading some of the answers given on this site.

Obviously I am missing a formal introduction to these topics hence the difficulty. So I am asking if introductory books on number theory like - "A Friendly Introduction to Number theory" or "A Gentle Introduction to Number Theory" would solve this problem?

$\endgroup$

marked as duplicate by MathematicianByMistake, Peter Foreman, YuiTo Cheng, Adrian Keister, Javi Jun 24 at 22:22

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ You might be able to find a table of contents, or even an index, for those books on line, and then check to see whether base conversion is covered. You could check some Discrete Math texts, too. $\endgroup$ – Gerry Myerson Jun 24 at 10:37
  • 1
    $\begingroup$ @MathematicianByMistake I have already said that I have read the answers here. The answer does not answer it in detail for me. Thats why I want a formal reference. $\endgroup$ – ng.newbie Jun 24 at 11:27
  • $\begingroup$ You wrote that you had read some of the answers on this site, but you didn't say which ones. How was anyone to know whether or not you had read any particular answer? $\endgroup$ – Gerry Myerson Jun 24 at 23:29
1
$\begingroup$

I will try an answer to the question behind your question: why the division algorithm works for base conversion.

Consider the integer $238$, say, in ordinary base $10$ notation. The units digit is the remainder when you divide that number by $10$. That's something you can understand several ways. One is "it's obvious". Or you can inspect the expansion $$ 238 = 200 + 30 + 8 . $$ Or you can invoke the division algorithm explicitly: $$ 238 = 23 \times 10 +8 . $$ However you understand it, you can proceed by subtracting the remainder $8$ and dividing by $10$ to get to $23$. Use that to find the ten's digit of $238$, and so on (in general).

Now stop thinking about "base conversion" and remember that an integer $n$ is just what it is, independent of how we choose to represent it with marks on a page. Then "converting to base $b$" is just "finding the digits for the base $b$ representation". There is nothing special about $10$ and the argument in the previous paragraph works just fine.

In practice, it's easy to be confused when writing out an actual conversion because you have to write the integers in our ordinary base $10$ along the way.

For example, to write $238$ in binary, begin by imagining that you have the answer. Then $$ 238 = ? \times 2^7 + ? \times 2^6 + ? \times 2^5 + ? \times 2^4 + ? \times 2^3 + ? \times 2^2 + ? \times 2^1 + ? \times 2^0, $$ and the problem is to find the "digits" $?$, each of which is $0$ or $1$. (You know the first term will be $1 \times 2^7$ because $128$ the highest power of $2$ that's smaller than $238$.)

Since all but the last term in the expansion is even, the remainder when you divide by $2$ will be the last term. That tells you the units digit, which is $0$ in this case. Now subtract that remainder (which is $0$) and divide by $2$ to get $119$. That's odd, so division by $2$ leaves the remainder $1$, which is the $2$s digit in the binary expansion of $238$. And so on.

$\endgroup$
  • $\begingroup$ Why is it important to collect the remainders? Look how I see it is - the number consists of 2 parts 100 and 3 parts 10 and 8 parts of 1. But I don't understand why dividing by 2 I can convert to binary. $\endgroup$ – ng.newbie Jun 24 at 11:46
  • $\begingroup$ Division is splitting the number into parts of the divisor, how does that help in the process? $\endgroup$ – ng.newbie Jun 24 at 11:50
  • 1
    $\begingroup$ I've worked an example. I've explained as best I can. If you're still confused you will have to ask elsewhere, or hope for a better answer here. I don't think you're likely to find an elementary text with a helpful "formal reference". $\endgroup$ – Ethan Bolker Jun 24 at 12:00
  • $\begingroup$ I understand now after the edit. Thanks. $\endgroup$ – ng.newbie Jun 25 at 14:04
0
$\begingroup$

Just as a base ten representation of a number splits it into a number of pieces of multiples of 10, so too does a binary representation split a number into pieces of multiples of two. For example, in binary, 101101 is one piece of $2^5$, one of $2^3$, one of $2^2$ and one of $2^0$, I.e.

$$2^5 +2^3 + 2^2 + 2^0 = 32 + 8 + 4 + 1 = 45.$$

The division algorithm is basically this process backwards. To find the largest "bit" in a binary representation, we need to find the largest power of 2 that divides the number. Then we need to repeat the process on the remainder so that we end up with something equal to the number we started.

For example, $45 = 22\cdot 2 + 1$, so we know our $2^0$ digit is the remainder, $1$. $22=2\cdot 11$, so our $2^1$ digit is $0$. $11= 2\cdot 5 + 1$, so our $2^2$ bit is $1$. $5= 2\cdot 2 + 1$, so our $2^3$ digit is $1$. $2= 1\cdot 2$, so our $2^4$ digit is $0$, our $2^5$ digit is $1$, and we're finished; $45$ in binary is $101101$

$\endgroup$
0
$\begingroup$

Let $n$ be any positive integer and let $b$ be a base. By the division algorithm we get that $$n=bq_0+r_0$$ where $r_0\in\{0,1,..,b-1\}$.

If $q_0\lt b$ then we are done. If not, then $$q_0=bq_1+r_1\implies n=b(bq_1+r_1)+r_0=b^2q_1+br_1+r_0$$.

If $q_1\lt b$ then we are done. What do you think happens if it is not?

Notice that we only divide the $q_i$s by $b$ and the remainders become the next digit, going from right to left.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.