For an integer and positive integer , Euclidean division writes with unique integer quotient and remainder . For , repeated quotient-and-remainder steps yield the digits of a base-p expansion when . The uniqueness follows because the difference of two permitted remainders cannot be a nonzero multiple of .
For an integer and positive integer , the remainder in Euclidean division is the unique integer in for which with an integer . It is not the full quotient .
Repeated division with remainder that determines successive digits of a quotient. To generate the fractional digits in base , multiply the current remainder by , divide by the denominator, and keep the resulting remainder for the next step.
For integers and , an integer division algorithm determines the binary numeral system digits of a quotient by testing and conditionally subtracting successively halved multiples of the divisor. The loop invariant , together with , makes each step a halving of the remaining quotient interval. Start with and large enough that . To decrease by one, subtract from and add to exactly when . Both branches preserve the displayed equality and establish . When , the quotient and remainder conditions hold.