Let's consider the problem of converting a number to base k. Initially I was confused by this algorithm, but the more I think about it the more it makes sense.

Consider the number 11. We want to convert it to base 3. Notice that the answer is 102 for the following reason:

10 = 1*3^2 + 0*3^1 + 2*3^0

When we start we don't actually know this factorization yet but it is what we want to get to. You can simply read off the coefficients of this expression and that's the base 3 number.

Because we know we can express any number in terms of a polynomial of this form (for any natural number base), let us turn to the problem of extracting these coefficients.

To make it easy, how would be extract the first coefficient? Well we would just use the modulus operator (by the base). So we do

10 % 3 =
(1*3^2 + 0*3^1 + 2*3^0) % 3 = 2

Notice that the modulus of all terms except the rightmost have a modulus of zero. This is because each of those terms have a factor of three. So doing the modulus reads off the rightmost coefficient.

Now consider the operation of integer division.

10 / 3 = 
(1*3^2 + 0*3^1 + 2*3^0) / 3 = 
(1*3^2)/3 + (0*3^1)/3 + (2*3^0)/3 = 
1*(3^2)/3 + 0*(3^1)/3 + 2*(3^0)/3 = 
1*[(3^2)/3] + 0*[(3^1)/3] + 2*[(3^0)/3] = 
1*(3^1) + 0*3^0 + 0 = 
1*(3^1) + 0*3^0

Notice the last term zeros out because there is no factor of 3.