Euclidean Division Algorithm Explained: a = bq + r With Examples

The Euclidean division algorithm, usually called the division algorithm, states that for any integers a and b with b ≠ 0 there exist unique integers q and r such that a = bq + r and 0 ≤ r < |b|. Taking a = 47 and b = 6 gives q = 7 and r = 5, since 47 = 6 × 7 + 5 and 5 is in the range 0 to 5.

Despite the name, it is not an algorithm at all. It is a theorem that makes two guarantees: the quotient and remainder always exist, and there is only one pair that qualifies. Long division is one procedure that finds them; the theorem is what makes finding them worthwhile.

This guide states the theorem precisely, explains where each condition comes from, proves existence and uniqueness in outline, handles all four sign cases, and shows why this result is the foundation under both the Euclidean algorithm and modular arithmetic.

The Formal Statement

Division Algorithm. Let a and b be integers with b ≠ 0. Then there exist unique integers q and r such that

a = bq + r with 0 ≤ r < |b|

The four numbers have fixed names:

Three conditions do the real work, and each one matters:

1. b ≠ 0. Division by zero is undefined, so the theorem simply excludes it.
2. r ≥ 0. The remainder is never negative under this convention. This is the choice that makes the pair unique.
3. r < |b|. The remainder is strictly smaller than the size of the divisor. The absolute value bars matter because b may be negative, and a remainder is never negative.

Why the Bound on r Is Necessary

Without the condition 0 ≤ r < |b|, the equation a = bq + r has infinitely many solutions. Taking a = 47 and b = 6:

47 = 6 × 5 + 17
47 = 6 × 6 + 11
47 = 6 × 7 +  5     ← the only one with 0 ≤ r < 6
47 = 6 × 8 −  1
47 = 6 × 9 −  7

Every line is a true equation. The bound is what selects exactly one of them as the answer.

Read the pattern: a remainder of 17 means at least two more copies of 6 still fit, so the quotient was too small. A remainder of −1 means the quotient overshot. Only r = 5 sits in the window where neither is true.

This is the same rule taught in schools as “the remainder must be smaller than the divisor”. The theorem is that statement made precise enough to prove.

Why q and r Exist

The argument is short and worth seeing.

Consider all numbers of the form a − bk as k runs through the integers, and keep only the non-negative ones:

S = { a − bk  :  k an integer, and a − bk ≥ 0 }

S is not empty. Choosing k negative enough (for positive b) makes a − bk as large as you like, so at least one non-negative value exists.

S has a smallest member. Any non-empty set of non-negative integers has a least element. Call it r, produced by some particular k, which we name q. So r = a − bq, which rearranges to a = bq + r.

That smallest r is below |b|. Suppose instead r ≥ |b|. Then r − |b| is still non-negative and still has the form a − bk for a different k, so it belongs to S and is smaller than r. That contradicts r being the least element. Therefore r < |b|.

Existence is proved. Notice that the argument never computes anything; it only shows that a smallest leftover has to exist.

Why q and r Are Unique

Suppose two pairs both work:

a = bq₁ + r₁     with 0 ≤ r₁ < |b|
a = bq₂ + r₂     with 0 ≤ r₂ < |b|

Subtracting one from the other:

0 = b(q₁ − q₂) + (r₁ − r₂)

so    r₂ − r₁ = b(q₁ − q₂)

The left side is a difference of two values both lying between 0 and |b| − 1, so its size is strictly less than |b|. The right side is a multiple of b, so its size is either 0 or at least |b|.

The only way both can be true is if the difference is 0. So r₁ = r₂, and then b(q₁ − q₂) = 0 with b ≠ 0 forces q₁ = q₂.

The two pairs were the same pair all along. Uniqueness is proved.

Positive Examples

Two rows deserve comment.

a = 5, b = 9. The divisor does not fit even once, so q = 0 and the whole dividend becomes the remainder. This is correct and often surprises people who expect the quotient to be at least 1.

a = −15, b = 5. The dividend is negative but the division is exact, so r = 0 with no complications. A remainder of 0 means b divides a exactly, which is what a remainder of zero means.

Negative Dividends and Divisors

This is where the theorem’s insistence on 0 ≤ r < |b| shows its teeth. All four sign combinations for a = ±47 and b = ±6:

The remainder is never negative, in any row. The quotient absorbs all the sign changes.

Take the second row carefully. The instinct is to write −47 = 6 × (−7) − 5, which is a true equation but has r = −5, outside the allowed range. Dropping the quotient one step further, to −8, gives 6 × (−8) = −48, and getting from −48 back up to −47 needs +1. So r = 1.

The rule for finding q by hand: round a ÷ b away from the direction that would make r negative. For positive b that means rounding down, and −47 ÷ 6 = −7.83… rounds down to −8. For negative b it means rounding up, and 47 ÷ (−6) = −7.83… rounds up to −7.

This is a convention, not the only one

Programming languages usually make a different choice. Under truncated division, used by C, Java and JavaScript, the quotient rounds toward zero and the remainder takes the sign of the dividend:

Euclidean:   -47 = 6 × (-8) + 1      remainder  1
Truncated:   -47 = 6 × (-7) - 5      remainder -5
Floored:     -47 = 6 × (-8) + 1      remainder  1

All three satisfy a = bq + r. They differ only in which q they select, and therefore in the sign of r. Floored and Euclidean agree whenever the divisor is positive, and part company only when b is negative.

The theorem in this article picks the Euclidean convention, so the remainder is always non-negative. The full comparison, and which language does what, is in the remainder of negative numbers, and the Modulo Calculator reports a mod n under all three.

How This Differs From Long Division

The two are often confused, and the distinction is worth being clear about.

Long division is one way of finding the pair the theorem promises. Repeated subtraction is another, and so is estimation. The theorem is what guarantees that all of them, done correctly, must land on the same answer, which is why a division has a single right answer at all.

If the goal is to carry out a division rather than to justify one, long division with remainders is the practical guide, and the Remainder Calculator does it in one step.

Connection to the Euclidean Algorithm

The division algorithm is what makes Euclid’s method for the greatest common divisor terminate.

Each step of the Euclidean algorithm applies the theorem once and then discards the quotient:

252 = 198 × 1 + 54
198 =  54 × 3 + 36
 54 =  36 × 1 + 18
 36 =  18 × 2 +  0

The condition 0 ≤ r < |b| guarantees that each new remainder is strictly smaller than the last and never drops below 0. A strictly decreasing sequence of non-negative integers cannot go on forever, so a remainder of 0 must be reached, and the algorithm stops.

Without the bound on r, there would be no guarantee of termination at all. The full method, and how it extends to produce Bézout coefficients, is covered in the extended Euclidean algorithm.

Connection to Modular Arithmetic

The theorem is also what makes modular arithmetic well defined.

Because q and r are unique, every integer a has exactly one remainder modulo n. That single value is the residue, and it is what assigns a to exactly one of the n residue classes. Without uniqueness, a number could belong to two classes at once and the whole system would collapse.

a ≡ r (mod n)     where r is the unique remainder from a = nq + r

The theorem also fixes the size of the system: since 0 ≤ r < n, there are exactly n possible residues, namely 0 through n − 1. That is why arithmetic modulo 12 has twelve classes and no more. The rules built on top of this are covered in modular arithmetic explained.

Practice Problems

Find the unique q and r with a = bq + r and 0 ≤ r < |b|.

1. a = 89, b = 13
2. a = 7, b = 20
3. a = −100, b = 7
4. a = −1, b = 4
5. a = 89, b = −13
6. a = −89, b = −13
7. a = −1,234, b = 50
8. Explain why a = 47, b = 6, q = 6, r = 11 is not a valid answer.

Answers

1. 13 × 6 = 78, and 89 − 78 = 11. q = 6, r = 11. Check: 11 < 13. ✓
2. The divisor is larger than the dividend, so q = 0, r = 7. Check: 20 × 0 + 7 = 7. ✓
3. 7 × (−15) = −105, and −105 + 5 = −100. q = −15, r = 5. Rounding −100 ÷ 7 = −14.28… down gives −15. ✓
4. q = −1, r = 3, since 4 × (−1) + 3 = −1 and 0 ≤ 3 < 4. Writing 4 × 0 − 1 gives r = −1, which is outside the range.
5. With b negative, round 89 ÷ (−13) = −6.85… up to −6. Then (−13) × (−6) = 78 and 89 − 78 = 11. q = −6, r = 11. ✓
6. (−13) × 7 = −91, and −91 + 2 = −89. q = 7, r = 2. Check: 0 ≤ 2 < 13. ✓
7. 50 × (−25) = −1,250, and −1,250 + 16 = −1,234. q = −25, r = 16. ✓
8. The equation itself is true, since 6 × 6 + 11 = 47. It fails the second condition: the remainder 11 is not less than the divisor 6. One more copy of 6 fits, so the correct pair is q = 7, r = 5.

Division Algorithm FAQ

What is the division algorithm in simple terms?

It says that dividing any whole number by any non-zero whole number always leaves exactly one valid quotient and one valid remainder, with the remainder somewhere from 0 up to one less than the size of the divisor. It guarantees a division has a single right answer.

Why is it called an algorithm if it is a theorem?

The name is historical and slightly misleading. It asserts existence and uniqueness rather than giving a procedure. Some textbooks avoid the confusion by calling it the quotient remainder theorem or the division theorem, which are the same result.

What is the difference between the division algorithm and the Euclidean algorithm?

The division algorithm is a single statement about one division. The Euclidean algorithm is a repeated procedure that applies it over and over to find a greatest common divisor. The first is what makes the second guaranteed to finish.

Why must the remainder be non-negative?

Because without that condition the pair (q, r) is not unique. Allowing negative remainders makes 47 = 6 × 8 − 1 just as valid as 47 = 6 × 7 + 5. Pinning r to the range 0 to |b| − 1 selects exactly one answer, which is what the theorem needs.

Does the theorem work when the divisor is negative?

Yes, and the remainder stays non-negative. That is why the bound is written with absolute value bars, r < |b|. Dividing 47 by −6 gives q = −7 and r = 5, since (−6) × (−7) + 5 = 47.

Can the quotient be zero?

Yes, whenever the dividend is smaller than the divisor. Dividing 5 by 9 gives q = 0 and r = 5. It can also be negative when the signs of a and b differ.

Is this the same as the remainder formula?

They are the same equation used for different purposes. Dividend = Divisor × Quotient + Remainder is the working formula for finding or checking a value, as used in how to find the remainder. The division algorithm adds the two claims that make it a theorem: such a pair always exists, and there is only one.

Does it apply to polynomials?

An analogous theorem does. For polynomials, the bound on the remainder is on degree rather than size: dividing f(x) by a non-zero g(x) gives unique q(x) and r(x) with r(x) either zero or of lower degree than g(x). That is the result behind polynomial long division and the Remainder Theorem.