Mathwords logoMathwords

Division Algorithm — Definition, Formula & Example

The division algorithm is the theorem that says dividing any integer by a positive integer always gives exactly one integer quotient and one remainder. The quotient may be negative. The remainder is never negative and is always smaller than the divisor.

For all integers aa and bb with b>0b > 0, there exist unique integers qq and rr such that a=bq+ra = bq + r and 0≤r<b0 \le r < b. Here q=⌊a/b⌋q = \lfloor a/b \rfloor. A common extension allows any b≠0b \neq 0 and requires 0≤r<∣b∣0 \le r < |b|. Despite its name, the statement is a theorem (existence and uniqueness), not a step-by-step procedure.

Key Formula

a=bq+r,0≤r<b,q=⌊ab⌋a = bq + r, \qquad 0 \le r < b, \qquad q = \left\lfloor \frac{a}{b} \right\rfloor
Where:
  • aa = the dividend, any integer
  • bb = the divisor, a positive integer
  • qq = the quotient, an integer (can be negative)
  • rr = the remainder, an integer with 0 ≤ r < b

Worked Example

Problem: Use the division algorithm to find the quotient q and remainder r when a = -17 is divided by b = 5.
Step 1: The quotient is the floor of a/b, which is the greatest integer less than or equal to -3.4. That integer is -4, not -3, because -3 is greater than -3.4.
q=⌊−175⌋=⌊−3.4⌋=−4q = \left\lfloor \frac{-17}{5} \right\rfloor = \lfloor -3.4 \rfloor = -4
Step 2: Solve a = bq + r for the remainder.
r=a−bq=−17−5(−4)=−17+20=3r = a - bq = -17 - 5(-4) = -17 + 20 = 3
Step 3: Check both conditions. The equation holds, and the remainder satisfies 0 ≤ 3 < 5.
5(−4)+3=−17,0≤3<55(-4) + 3 = -17, \qquad 0 \le 3 < 5
Answer: q = -4 and r = 3, so -17 = 5(-4) + 3.

Why It Matters

The Euclidean algorithm for computing greatest common divisors is just the division algorithm applied repeatedly. In an introductory number theory or discrete math course, the theorem also underlies modular arithmetic. It explains why every integer is congruent mod b to exactly one of 0, 1, ..., b − 1, so the remainders form the residue classes of an equivalence relation.

Common Mistakes

Mistake: Writing -17 = 5(-3) + (-2) and calling -2 the remainder, because a calculator truncates -3.4 toward zero.
Correction: The equation is true, but -2 breaks the condition 0 ≤ r < b. Round the quotient down (take the floor), not toward zero. That gives q = -4 and r = 3.

Related Terms

  • Standard Algorithm — Long-division procedure that computes the quotient and remainder
  • Integer Division — Operation whose quotient and remainder the theorem describes
  • Equivalence Relation — Congruence mod b groups integers by remainder
  • Remainder — Leftover amount the theorem guarantees is nonnegative and smaller
  • Quotient — Integer result the theorem says is unique
  • Euclidean Algorithm — Method that repeatedly applies the division algorithm to find GCDs