One possible reason the textbook fails to give the reason for the correctness of this algorithm is that the authors thought it would be above the average reader's level. So I wanted to see if you can at least pose the problem rigorously, which is both a necessary and a significant step towards the solution.

OK, one way to define the

*k*th digit (k = 1, 2, ...) of n base b counting from the right is (n / b

^{k-1}) % b. Here (x / y) is the result of integer division and (x % y) is the remainder when x is divided by y (borrowing the notation from the C programming language). Indeed, (n / b

^{k-1}) is n without the rightmost k - 1 digits, and % b returns the last digit of the result. For example, the 3rd (from the right) digit of 1354 is (1354 / 100) % 10 = 13 % 10 = 3.

The algorithm repeatedly divides n by b and takes the remainder of the result. According to the algorithm, the

*k*th digit of n is $\displaystyle \underbrace{[(\dots((n/b)/b)/\dots)/b]}_{k-1\text{ divisions}}\mathbin{\%}b$.

Now, $\displaystyle (\dots((n/b)/b)/\dots)/b=n/b^{k-1}$. This can be shown as follows. We have $\displaystyle x/y=\left\lfloor\frac{x}{y}\right\rfloor$ where $\displaystyle \lfloor\cdot\rfloor$ is the

floor function, $\displaystyle x/y$ is integer division and $\displaystyle \frac{x}{y}$ is regular division. And

Wikipedia claims that $\displaystyle \left\lfloor \frac{\lfloor x/m\rfloor}{n} \right\rfloor = \left\lfloor \frac{x}{mn} \right\rfloor$ for positive integers m, n and arbitrary real number x, i.e., (x / m) / n = (x / mn).

Thus, the

*k*th digit of n returned by the algorithm is (n / b

^{k-1}) % b, which is exactly the definition.

Thinking again about this, it's not unreasonable to adopt the definition that the digits of n base b are the ones returned by this algorithm; then there is nothing to prove! Of course, if the definition is different from the ones above, then the proof has to change accordingly.