The Division Algorithm

In this class we will develop the division algorithm as the principle that formalizes, for integers, the unique decomposition b=qa+r with 0\le r<|a|. The existence of the quotient and the remainder is first proved, and then their uniqueness. Finally, the meaning of the remainder is interpreted, the theory is linked to the long division algorithm as a computational procedure, and its natural connection with modular arithmetic and computational applications is anticipated.

Learning Objectives

Upon completing this class, the student will be able to:

1. Identify the basic concepts and roles of integer division (dividend, divisor, quotient, remainder) and the notion of divisibility as the exact case.
2. Explain the statement of the Euclidean division algorithm/theorem, including the conditions that determine the remainder (0\le r<|a|) and their purpose in avoiding ambiguities.
3. Apply the Euclidean decomposition b=qa+r to determine q and r in concrete examples, verifying the bound on the remainder.
4. Analyze the treatment of cases according to the sign of the dividend and the divisor, justifying why the Euclidean convention maintains a nonnegative remainder.
5. Execute the long division algorithm as a mechanical procedure based on positional representation to obtain q and r.

TABLE OF CONTENTS:
Division and divisibility
Euclidean division theorem
Proof of the Euclidean division theorem
Interpretation of the quotient and the remainder
Long division algorithm
Conclusion
Proposed and solved exercises

Division and divisibility

In arithmetic, divisibility describes the “exact” case: a\mid b means that b can be written exactly as a multiple of a. However, although divisibility does not always hold between two arbitrary integers, we can still ask “how many times one number fits into another and, if it does not fit exactly, what is left over.” This is the context in which the division algorithm arises, guaranteeing that any integer b can be written as a multiple of a plus a “remainder.”

As an example, consider a=3 and b=16. It is clear that 3 does not divide 16. Nevertheless, it is possible to find a quotient and a remainder for the division operation, because

16 = 5\cdot 3 + 1

Consequently, when dividing b=16 by a=3 (where b is the dividend and a is the divisor), represented by 16/3 or 16\div 3, the quotient obtained is q=5 and the remainder is r=1. In general, the division algorithm states that, for any integers a (divisor) and b (dividend) with a\neq 0, there exist unique integers q and r such that

b=qa+r,\qquad 0\le r<|a|

In this example, 16=3\cdot 5+1, and the condition 0\le r<|a| is satisfied because 0\le 1<3. This formulation avoids ambiguities when the divisor (or the dividend) may be negative and guarantees that the remainder is always nonnegative and strictly less than the absolute value of the divisor.

Euclidean Division Theorem

The result of applying the division algorithm is what is known as Euclidean division and is based on the following result.

Theorem: Let a,b\in\mathbb{Z} with a\neq 0. Then there exist unique q,r\in\mathbb{Z} such that

b=qa+r,\qquad 0\le r<|a|.

The integer q is called the quotient and r is called the remainder of the division of b by a.

Proof of the Euclidean Division Theorem

This proof is divided into two parts: first, the existence of the quotient and the remainder is established; and then, given their existence, their uniqueness is shown.

Existence

Let a,b\in\mathbb{Z} with a\neq 0 and define d=|a|, so that d>0. We will first prove the case b\ge 0: we will show that there exist q,r\in\mathbb{Z} such that b=dq+r and 0\le r<d. We will then address the case b<0. Finally, we will replace d by |a| to obtain the form b=qa+r with 0\le r<|a|.

For b\in\mathbb{Z} with b\ge 0, we establish the proposition P(b): “there exist q,r\in\mathbb{Z} such that b=dq+r and 0\le r<d.” We will prove by induction that P(b) holds for all b\ge 0.

Base case: For b=0, taking q=0 and r=0 yields 0=d\cdot 0+0 and 0\le 0<d. Therefore, P(0) is true.

Inductive step: Let k\ge 0 and suppose that P(k) is true. Then there exist q,r\in\mathbb{Z} such that

k=dq+r,\qquad 0\le r<d.

Adding 1 to both sides yields

k+1=dq+(r+1).

Moreover, from 0\le r<d it follows that r+1\le d. Consequently, only the cases r+1<d or r+1=d can occur.

Case 1: If r+1<d, we define q'=q and r'=r+1. Then

k+1=dq'+r',\qquad 0\le r'<d.

Case 2: If r+1=d, then k+1=dq+d=d(q+1)+0. We define q'=q+1 and r'=0, and we have

k+1=dq'+r',\qquad 0\le r'<d.

In both cases we have constructed integers q',r' such that k+1=dq'+r' and 0\le r'<d. Therefore, P(k+1) is true. We conclude by induction that P(b) holds for all b\ge 0.

Now consider the case b<0. Then -b>0. Applying the previous result to -b, there exist q,r\in\mathbb{Z} such that

-b=dq+r,\qquad 0\le r<d.

Multiplying by -1 yields

b=-dq-r.

If r=0, it suffices to take q_1=-q and r_1=0, so that b=dq_1+r_1 and 0\le r_1<d.

If r>0, we define q_1=-q-1 and r_1=d-r. Since 0<r<d, we have 0<d-r<d, that is, 0\le r_1<d. Moreover,

dq_1+r_1=d(-q-1)+(d-r)=-dq-d+d-r=-dq-r=b.

Consequently, for every b\in\mathbb{Z} there exist q_1,r_1\in\mathbb{Z} such that b=dq_1+r_1 and 0\le r_1<d.

Finally, recall that d=|a|. If a>0, then d=a and the equality b=dq_1+r_1 can be written as b=aq_1+r_1, with 0\le r_1<|a|.

If a<0, then d=-a and b=dq_1+r_1=(-a)q_1+r_1=a(-q_1)+r_1. Defining q=-q_1 and r=r_1, we obtain

b=qa+r,\qquad 0\le r<|a|.

This completes the proof of the existence of q and r for any a,b\in\mathbb{Z} with a\neq 0.

Uniqueness

Suppose that there exist q,q',r,r'\in\mathbb{Z} such that

b=qa+r=q'a+r',\qquad 0\le r,r'<|a|.

Subtracting both expressions yields

a(q-q')=r'-r.

Since 0\le r,r'<|a|, it follows that |r'-r|<|a|. On the other hand, the left-hand side is a multiple of a, and therefore also a multiple of |a|. The only integer multiple of |a| with absolute value strictly less than |a| is 0; indeed, if |a| m \neq 0 with m\in\mathbb{Z}, then \big| |a| m \big| \ge |a| . Consequently, r'-r=0, that is, r=r', and substituting into b=qa+r yields q=q'. Hence the decomposition is unique.

Interpretation of the Quotient and the Remainder

• What “remainder” means. If b=qa+r, then r=b-qa is what “remains” after removing from b the multiple qa. In other words, r is the residue obtained by fitting b to the grid of multiples of a.
• Why it is required that 0\le r<|a|. Without this condition, the pair (q,r) would not be unique. Indeed, if b=qa+r, then also b=a(q+1)+(r-a). The condition 0\le r<|a| forces the remainder to lie in a fixed window \{0,1,2,\dots,|a|-1\}, thereby preventing the infinitely many “relabelings” of the same number.
• What happens if a is negative. The theorem remains valid without changes: the remainder stays nonnegative and bounded by |a|. This is relevant because some programming languages use truncation toward zero and may produce negative remainders, whereas in mathematics the convention 0\le r<|a| is adopted so that the remainder is a “standard” representative.

  Moreover, when a>0, the quotient coincides with the floor:

  q=\left\lfloor \frac{b}{a}\right\rfloor,\qquad r=b-a\left\lfloor \frac{b}{a}\right\rfloor.

Long Division Algorithm

Starting from Euclidean division, it is possible to implement the long division algorithm by taking advantage of the positional representation of numbers. This algorithm is a computational technique that allows one to quickly find the values q and r when one wishes to compute b\div a with a,b\in\mathbb{Z} and a\neq 0.

To describe it, we first review some examples that illustrate the process and the possible situations that may arise during the execution of the algorithm.

1. Suppose that we want to compute 57\div 4. Here 57 is the dividend and 4 is the divisor. To do so, we perform the following sequence of calculations:

   \begin{array}{rll} (1) & \color{red}57 \div 4 =\color{black} \\ & \text{Write the division operation.} \\ \\ (2) & \color{red}5'\color{black}7 \div 4 = \\ & \text{Separate the first prefix (from the left) of the dividend that}\\ &\text{is greater than or equal to the divisor, in this case 5.} \\ \\ (3) & 5'7 \div 4 = \color{red}1\color{black} \\ & \text{Think of the greatest number that, when multiplied by $4$,}\\ &\text{is less than or equal to $5$, and write it to the right of the equality. It is 1.} \\ \\ (4) & \begin{array}{ll}\phantom{-|}5'7 \div 4 &= 1 \\ \color{red}-|\underline{4}\color{black} & \\ \color{red}\phantom{-|}1\color{black} & \end{array} \\ & \text{Multiply the result by the divisor and subtract it from the selected value.} \\ \\ (5) & \begin{array}{ll}\phantom{-|}5'\color{red}7'\color{black} \div 4 &= 1 \\ -|\underline{4} & \\ \phantom{-|}1\color{red}7\color{black} & \end{array} \\ & \text{Select and “bring down” the next digit.} \\ \\ (6) & \begin{array}{ll}\phantom{-|}5'7' \div 4 &= 1\color{red}4\color{black} \\ -|\underline{4} & \\ \phantom{-|}17 & \\ \color{red}-|\underline{16}\color{black} & \\ \color{red}\phantom{-|}1\color{black} \end{array} \\ & \text{Repeat the sequence with the last number obtained.} \end{array}

   The algorithm ends when there are no more digits to “bring down,” yielding as a result the quotient q=14 and the remainder r=1. In particular, the remainder will always be smaller than the divisor.

2. Suppose that we want to compute 132\div 5. To do so, we perform the following sequence of calculations:

   \begin{array}{rl} (1) &1'32 \div 5 = \\ & \text{Separate the first prefix of the dividend and look for a natural number that,}\\ & \text{when multiplied by 5, is less than or equal to it. If this is not possible,}\\ & \text{incorporate the next digit until it becomes possible.} \\ \\ (2) &\begin{array}{ll}\phantom{-|}13'2 \div 5 &= 2 \\ -|\underline{10} & \\ \phantom{-|1}3 & \end{array}\\ & \text{Once the previous step works, execute the algorithm normally.} \\ \\ (3) &\begin{array}{ll}\phantom{-|}13'2' \div 5 &= 26 \\ -|\underline{10} & \\ \phantom{-|1}32 & \\ \phantom{\,} -|\underline{30} & \\ \phantom{-|30} 2 & \end{array} \end{array}

3. If the dividend has more digits, the procedure is carried out in the same way. For example, when computing 3521\div 12, one obtains:

   \begin{array}{ll} \phantom{-|}35'2'1' \div 12 & = 293 \\ -|\underline{24} & \\ \phantom{-|}112 & \\ -|\underline{108} & \\ \phantom{-|10}41 & \\ \phantom{0}-|\underline{36} & \\ \phantom{10-|}5 & \\ \end{array}

4. If one of the numbers is negative, there are two acceptable ways to present the result. However, the standard form in number theory is the one in which the remainder is positive and therefore consistent with Euclidean division. For example, if we compute -598\div 21, the following possible developments are obtained, both correct as identities:

   • With a negative remainder: This is obtained by removing the sign at the beginning of the operation and restoring it at the end.

     \begin{array}{ll} \phantom{-}59'8' \div 21 &= 28 \\ -|\underline{42} & \\ \phantom{-|'}178 & \\ \phantom{\,}-|\underline{168} & \\ \phantom{-|00}10 & \\ \end{array}

     From this, we have:

     598 = 21 \times 28 + 10

     Then, if we multiply the entire equality by -1, we obtain:

     -598 = 21 \times (-28) - 10

     Thus, in this representation, the result of -598\div 21 is quotient q=-28 and remainder r=-10.

     And if we multiply the entire equality once again by -1, we obtain:

     598 = (-21)\times(-28) + 10

     Thus, the result of 598\div (-21) is quotient q=-28 and remainder r=10.

   • With a positive remainder and consistent with Euclidean division: From the previous development we have:

     -598 = 21 \times (-28) - 10

     Then, by adding 0=21-21 to the right-hand side of this equality, we obtain:

     -598 = 21 \times (-28) - 10 \color{red}+ 21 - 21\color{black} = 21\times(-29) + 11

     Therefore, being consistent with Euclidean division, the result of computing -598\div 21 yields a quotient q=-29 and the remainder r=11.

   With respect to the convention in Euclidean division, only the result with a positive remainder corresponds to the Euclidean quotient and remainder. However, both expressions are correct identities and may be useful in different contexts. Although the long division algorithm may produce negative remainders, this is practical for obtaining results mechanically and for performing algebraic manipulations without additional steps. On the other hand, results with a positive remainder, consistent with Euclidean division, allow one to fix a canonical representative of each residue class (for example, in \{0,1,\dots,n-1\}), which facilitates the precise and unambiguous labeling of integers. It should be noted that other conventions for representatives also exist, such as symmetric residues, which are equally valid once the rule is fixed.

Conclusion

The division algorithm guarantees that every integer division can be expressed uniquely as b=qa+r with 0\le r<|a|, thereby establishing a standard criterion for interpreting the quotient and the remainder even when negative numbers are involved. The long division algorithm is nothing more than a practical implementation of this decomposition, supported by positional representation, and it allows one to compute q and r mechanically. Finally, this Euclidean form not only avoids ambiguities, but also connects naturally with modular arithmetic: the remainder r acts as a canonical representative of the residue class of b modulo a, forming the basis of many techniques in number theory and in computational applications that will be addressed in future installments.

Proposed and Solved Exercises

Euclidean division

1. (solved) Find q and r such that

   137 = 9q + r,\qquad 0\le r\lt 9.

   Solution: Find the largest number that, when multiplied by 9, does not exceed 137. We have 15\times 9 = 135 and 16\times 9 = 144; therefore, the desired quotient is q=15. Now compute the remainder r=137-9q and verify that 0\le r\lt 9. Carrying out the verification, we obtain:

   r=137-9\cdot 15=137-135=2.

   Therefore, 137=9\cdot 15+2 with 0\le 2\lt 9.

2. (solved) Find q and r such that

   2025 = 37q + r,\qquad 0\le r\lt 37.

   Solution: Find the largest number that, when multiplied by 37, does not exceed 2025. Observe that 37\times 54 = 1998 and 37\times 55 = 2035; therefore, the desired quotient is q=54. Now compute the remainder r=2025-37q and verify that 0\le r\lt 37. Carrying out the verification, we obtain:

   r=2025-37\cdot 54=2025-1998=27.

   Therefore, 2025=37\cdot 54+27 with 0\le 27\lt 37.

3. Find q and r such that

   745 = 23q + r,\qquad 0\le r\lt 23.

4. Find q and r such that

   -314 = 11q + r,\qquad 0\le r\lt 11.

5. Find q and r such that

   598 = (-21)q + r,\qquad 0\le r\lt |-21|.

6. Fixed remainder and search for integers. Let a=12.

   (a) Describe the set of all integers b whose Euclidean division by 12 has remainder r=5.

   (b) Find the smallest integer b\gt 1000 that satisfies the above and determine the corresponding quotient q.

Long Division Algorithm

In each case, apply the long division algorithm to compute the quotient q and the remainder r. Convert the result to Euclidean division when the algorithm yields a negative remainder.

1. 84\div 6.
2. 197\div 8.
3. 1256\div 7.
4. -3521\div 12.
5. -98765\div 24.
6. 845\div -13.
7. -12345\div -37.