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?
On
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$
On
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.
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.