The Division Algorithm for Integers

1. From Long Division to a Formal Algorithm

At its heart, the Division Algorithm is a precise statement about the outcome of long division. It tells us that when we divide one integer by another (positive) integer, we get a unique integer quotient and a unique non-negative remainder.

To see this in action, let's watch a short video that connects the familiar process of long division to this more formal idea. Pay close attention to the example with a negative number toward the end; it highlights a key rule we'll be focusing on.

As the video demonstrates, any division problem can be rewritten as an equation. For example, 327 ÷ 6 yields a quotient of 54 and a remainder of 3, which we can write as:

$327=(54\times 6)+3$

The key insight, especially from the example with -21, is that we must adjust the quotient q so that the remainder r is always non-negative. This constraint is central to the formal statement of the algorithm.

2. The Division Algorithm: A Formal Statement

Now let's state the theorem formally. This is one of the most fundamental theorems in number theory.

To summarize the key points from the reading:

Theorem: The Division Algorithm

If $a$ and $b$ are integers and $b>0$, then there exist unique integers $q$ and $r$ such that:

$a=bq+r\text{and}0\le r<b$

Let's break this down:

• $a$ is the dividend (the number being divided).
• $b$ is the divisor (the number we are dividing by, which must be positive).
• $q$ is the quotient (the integer result of the division).
• $r$ is the remainder (what's left over).

The two most important takeaways from this formal statement are:

1. Uniqueness: For any pair of integers $a$ and $b$ (with $b>0$), there is one and only one pair of integers q and r that satisfies the conditions.
2. The Remainder's Constraint: The condition $0\le r<b$ is crucial. The remainder must be non-negative and strictly less than the divisor. This is why in the video's example of $-21÷9$, the remainder had to be 6 (and the quotient -3), not -3.

Given your background in writing proofs, you might find the proof itself interesting. It relies on the Well-Ordering Principle, which states that any non-empty set of non-negative integers must contain a smallest element. The proof uses this principle to establish the existence of the remainder r, and then uses proof by contradiction to show that q and r are unique. You can find the full proof in the section immediately following the theorem statement in the same resource, 1.5: The Division Algorithm, if you're curious.

3. Applying the Algorithm: Calculations

Knowing the theorem is one thing; applying it is the key skill. Let's work through a few examples, paying special attention to negative numbers.

Example 1: a = 58, b = 7

We want to find q and r such that $58=7q+r$ with $0\le r<7$.
Standard division tells us that $58÷7$ is 8 with a remainder.
$58=7\times 8+2$.
Here, $q=8$ and $r=2$. This is a valid solution because $0\le 2<7$.

Example 2: a = -58, b = 7

This case is more subtle. If you use a calculator, $-58÷7\approx -8.28$. It's tempting to choose $q=-8$. Let's see what happens:
$-58=7\times (-8)+r$
$-58=-56+r$
$r=-2$
This is incorrect because the remainder r must be non-negative. To fix this, we need to choose a more negative quotient. Let's try $q=-9$:
$-58=7\times (-9)+r$
$-58=-63+r$
$r=5$
This is the correct answer. We have $q=-9$ and $r=5$, and this works because the condition $0\le 5<7$ is satisfied.

A helpful way to think about the quotient q is that it's the integer such that bq is the first multiple of b that is less than or equal to a.

Now, it's your turn to practice.

For more practice, I recommend trying the problems in "Exercise 1.5.1" from the Mathematics LibreTexts resource we looked at earlier.

Conclusion

In this lesson, we established the first building block of our number theory toolkit.

Key Takeaways:

• The Division Algorithm states that for any integer a and positive integer b, there are unique integers q (quotient) and r (remainder) such that $a=bq+r$.
• The most important constraint is that the remainder r must be non-negative and strictly less than the divisor b ($0\le r<b$).
• When working with a negative dividend a, you must choose the quotient q carefully to ensure the remainder r is non-negative. This usually means choosing a quotient that is "more negative" than a calculator might suggest.

This algorithm might seem simple, but its guarantee of a unique, well-behaved remainder is incredibly powerful.

Preview of the Next Lesson:
In our next lesson, we will use the Division Algorithm as a repeating step in a new process: the Euclidean Algorithm. This famous algorithm is a remarkably efficient way to find the greatest common divisor (GCD) of two integers. The image below gives a sneak peek of how this works—notice how the equation "Dividend = Divisor × Quotient + Remainder" is applied again and again.