arithmetic
Lets say we are running the long division algorithm (this long division algorithm) on two integers $A,B$ and we want to compute $\frac{B}{A}$. Why are we guaranteed to never have to place a digit greater than or equal to $10$ at the top of the division bracket?
Why is this guaranteed to be the case?
An ideal explanation will draw on the fact that we use a base 10 number system.
Consider the number $133/10$ using integer division. There are two subtractions that occur: first, $133\equiv 3\pmod {10}$ and so $3$ is subtracted. Next, dividing by $10$ is the same as subtracting $13\cdot (10-1)=13\cdot 9=117$ from $133-3=130$ leaving $133-3-117=13$.
This is the case primarily because division is the process of scaling the numerator by the amount required to scale the divisor to $1$. This is another way of saying that $a/b = a-\frac {a-a\mod b}b \cdot (b-1)-a\mod b$.
An unfortunate truth about converting a number from base $a$ to base $b$ is that unless there are integers $m > 0$ and $n > 0$ such that $a^m = b^n$, you need to use an arbitrarily large amount of memory in order to convert arbitrarily large numbers from base $a$ to base $b$ -- not necessarily all the digits all the time, but a lot of the digits a lot of the time. When $a^m = b^n$ (such as the conversion between $a=2^8$ and $b=2^5,$ which was mentioned in the question, where $a^5 = b^8$), you are able to "chunk" the input string of digits into groups of $m$ digits that can be converted into groups of $n$ digits, one group at a time with no kind of "carry" or interaction between the groups other than simply concatenating the digits to the output, exactly as described in the question; but that is a special case.
Suppose there are no such numbers $m$ and $n$. There are various ways this can happen, classified by the prime factorizations of $a$ and $b$:
Note that in the case where $a$ and $b$ are both powers of the same prime, there is always a way to read and convert one block of digits at a time, provided that you either start with the least significant digit or you know how many digits each number contains.
In the case where $b$ has a prime factor that $a$ does not have, there is no power of $a$ that will ever be divisible by $b$, so if we take an arbitrarily large $m$, we can make $a^m$ have as many significant digits in base $b$ as we want. So when converting an arbitrarily large number from base $a$ to base $b$, there is no limit on the size of the block of digits of the output that could be affected by whether some high-place-value digit of input happens to be $0$ or $1$. Conversely, when converting from base $b$ to base $a$, there is no limit on the size of the block of digits of the input that we would have to examine in order to know for sure what the value of some high-place-value digit of the output is. So both conversion directions take unbounded memory if one base has a factor the other does not have.
In the case where the two bases have the same prime factors, but the powers of the prime factors are not in the same ratio, for any large-enough integer $m$, $a^m$ will be divisible by $b^n$ for some integer $n > 0$. But the quotient $a^m/b^n$will always contain some number of "uncancelled" prime factors, and we can show that the number of these factors grows without bound as $m$ grows arbitrarily large.
At this point I want to introduce some mathematical notation: for $p$ a prime, $\nu_p(x)$ is the number of factors of $p$ in a prime factorization of $x$; for example, $\nu_2(60) = 2$ because $60 = 2^2\cdot3\cdot5$.
Now for each prime factor $p$ of $a$ and $b$, evaluate $\nu_p(a)/\nu_p(b)$; let $q$ be the prime factor of $a$ and $b$ that minimizes this ratio, $r$ the prime factor that maximizes it. Then $\nu_q(a^{\nu_q(b)}) = \nu_q(b^{\nu_q(a)})$; in fact, $a^{\nu_q(b)}$ is divisible by $b^{\nu_q(a)}$, because for every other prime factor $p$, $\nu_p(a^{\nu_q(b)}) \geq \nu_p(b^{\nu_q(a)})$. But the quotient $a^{\nu_q(b)}/b^{\nu_q(a)}$ is not divisible by $b$; it has at least one prime factor of $r$ and no prime factor $q$. That is, $a^{\nu_q(b)}$ has at least one "uncancelled" factor of $r$ when we take the greatest power of $b$ that divides $a^{\nu_q(b)}$.
If we next consider $a^{2\nu_q(b)}$, the highest power of $b$ that divides it is $b^{2\nu_q(a)}$, and after that division there are at least two "uncancelled" factors of $r$. In general, $a^{k\nu_q(b)}$ has at least $k$ "uncancelled" factors of $r$; to write $a^{k\nu_q(b)}$ in base $b$, we would have to write some multiple of $r^k$ not divisible by $b$ followed by some zeros. This base-$b$ numeral could have as many significant digits as we want, depending on how large $k$ is. So once again, an arbitrarily large number of digits of the base-$b$ output can depend on the value of a single high-place-value digit of the base-$a$ input, and there is no bound on how much memory we might require to convert an arbitrarily large number.
The conversions where we can convert blocks of digits one at a time in bounded memory are just the ones where the two bases have exactly the same prime factors, and the powers of those prime factors are in the same proportions. This implies both bases are powers of the same integer. For example, every three digits in base $36 = 2^2\cdot3^2 = 6^2$ can be converted to two digits of base $216 = 2^3\cdot3^3 = 6^3$.
Note that base-85 encoding of a string of (for example) $1024$ binary digits does not produce a number written in base $85$. Instead, it produces something like a mixed-radix number, but with more complex rules for "carryover" than more well-known mixed-radix systems (such as the time of day) typically have. Reading from right to left, the place values of a base-85 encoding of a $1024$-bit integer would be $1$, $85$, $85^2$, $85^3$, $85^4$, $2^{32}$, $85\cdot2^{32}$, $85^2\cdot2^{32}$, $85^3\cdot2^{32}$, $85^4\cdot2^{32}$, $2^{64}$, $85\cdot2^{64}$, and so forth. You might say that the so-called "base-85" encoding really encodes a string of bits as a base-$2^{32}$ numeral, except that rather than define a sequence of $2^{32}$ unique glyphs for the digits $0$ to $2^{32}-1$, we write each base-$2^{32}$ digit as a five-digit base-$85$ integer in that range, left-padded with zeros as needed.
By the way, for a conversion from base $a$ to base $b$ where the bases are not powers of the same integer and therefore there is no simple $n$-digit-to-$m$-digit conversion, it is still not ever necessary to use a division algorithm. You just have to work out how to multiple a base-$b$ number by $a$ in base $b$. For example, $723_{10}$ to base $16$:
First represent base $a=10$ in base $b=16$. In base $16$, the number $10_{10}$ is written $\mathrm a_{16}$.
Take the leftmost digit, $7.$ The intermediate result is $7_{16}.$
Multiply by $\mathrm a_{16}$. Result: $7_{16} \times \mathrm a_{16} = 46_{16}.$
Add the next digit from the input, $2.$ Result: $48_{16}.$
Multiply by $\mathrm a_{16}$. Result: $40_{16} \times\mathrm a_{16} + 8_{16} \times\mathrm a_{16} = 280_{16} + 50_{16} = 2\mathrm{d}0_{16}.$
Add the next digit from the input, $3.$ Result: $2\mathrm{d}3_{16}.$
Since that is the last digit of input, the final result is $2\mathrm{d}3_{16}.$
When base $b$ is smaller than base $a,$ the individual digits of the base-$a$ number will sometimes come out to multiple digits in base $b,$ but the idea is the same; just add them to the intermediate results.
Best Answer
At the first step, even if the first digit of the dividend (5, in the given example) is greater than divisor $d$, the result of the division cannot be greater than 9.
At subsequent steps, you start with a remainder $r$ satisfying $r\le d-1$. Putting a single digit $s$ at its right you get a new number $r'$: $$ r'=10r+s<10(r+1)\le 10d. $$ Hence $r'<10d$ and $r'\div d <10$, so we always get a single-digit result.