Let us consider short division, by which we mean a multiple-digit number divided by a single digit (see, e.g., post on number representation). We will assume , and .

We are interested in a quotient and a remainder such that with . Using that and we can deduce that which means that can be represented using or digits: (we may have in which case ).

We now have the following straightforward algorithm:

**Algorithm S**. Given and with and , this algorithm computes the quotient (we may have in which case if ) and the remainder such that , .

**S1**. Set , .**S2**. Set , .**S3**. If then exit. Otherwise set and go to step**S2**.

By the definition of integer division and modulus, the quantities in step **S2** imply for . Using this, we can show the correctness of the algorithm:

since . It is clear from the definition of that for . Considering now the definition of we see that since we will have for .

Note two important things: During the course of the algorithm, we only need to keep track of one -value, not one for each (it just made the analysis easier). Note also that each entry of can be overwritten with the coefficients/digits of , possibly saving some storage.