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

.

Now,

. This can be shown as follows. We have

where

is the

floor function,

is integer division and

is regular division. And

Wikipedia claims that

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.