Here’s the proof of uniqueness of $q$ and $r$ in the Division Theorem.
Let $n$ and $d \gt 0$ be arbitrary integers. By Lemma 4.4, there exist integers $q$ and $r$ such that $n = d \cdot q + r$ and $0 \leq r \lt d$. We want to show that $q$ and $r$ are unique.
Suppose that there exist integers $q_1, r_1, q_2, r_2$ such that $n = d \cdot q_1 + r_1$ and $n = d \cdot q_2 + r_2$ with $0 \leq r_1, r_2 \lt d$. Without loss of generality, let $r_1 \geq r_2$ and consider the following system of equations \begin{align*} n &= q_1 \cdot d + r_1 \\ n &= q_2 \cdot d + r_2. \end{align*} Subtracting gives us $0 = (q_1 - q_2) \cdot d + (r_1 - r_2)$. Rearranging this equation gives us $(q_2 - q_1) \cdot d = r_1 - r_2$. Since $(q_2 - q_1)$ is an integer, we have $d \mid (r_1 - r_2)$ by definition of divisibility. Since $0 \leq r_1 - r_2 \lt d$, we have $r_1 - r_2 = 0$ and therefore $r_1 = r_2$. Then from above, this gives us $(q_2 - q_1) \cdot d = 0$. Since $d \gt 0$, we have $q_2 - q_1 = 0$ and therefore $q_1 = q_2$. Thus, we have shown that $q$ and $r$ are unique.
What does the statement “without loss of generality” mean? Consider the scenario in which we used it: when we considered $r_1$ and $r_2$, we said “without loss of generality” and set $r_1 \geq r_2$. We were really pre-emptively dealing with the question: We said $r_1 \geq r_2$, but what if $r_2 \geq r_1$ instead?
It’s true: we had one of two situations on our hands: $r_1 \geq r_2$ or $r_2 \geq r_1$. That is, the particular fact we were working with was a statement of the form $p \vee q$.
How does one make use of a statement of the form $p \vee q$? Unlike a statement of the form $p \wedge q$, we can’t say that $p$ is definitely true or $q$ is definitely true. We know that at least one of them is true but we don’t know which. So we have to assume each of $p$ and $q$ and show that from either assumption, we can construct an appropriate proof. This is sometimes known as proof by cases. Here, $p$ and $q$ are our cases. There’s an inference rule for this: \[\frac{\begin{matrix} \\ \\ p \vee q \end{matrix} \quad \boxed{\begin{matrix}p \\ \vdots \\ r \end{matrix}} \quad \boxed{\begin{matrix}q \\ \vdots \\ r \end{matrix}}}{r} \vee\!e\] What is this saying? Suppose we want to prove some proposition $r$ by using the proposition $p \vee q$. What we need to do is consider the $p$ case and show that we can arrive at $r$ and then consider the $q$ case and show that we can also arrive at $r$.
In other words, we do the following:
So what we needed to do to prove our statement was to consider two cases: $r_1 \geq r_2$ and $r_2 \geq r_1$.
But what does “without loss of generality” mean here? We make the observation that if we carried out a proof for the other case, the proof would look exactly the same! The only things that would change would be the positions of $r_1$ and $r_2$. It’s not very interesting to see the exact same proof twice, so mathematicians invented some language, “without loss of generality”, to say to the reader that, look, the other case will basically give you the same proof but with the names swapped, so we’ll only do it once.
You might recall that all of the numbers we discussed in the Division Theorem actually have names (which is why we use certain letters to name them):
We are particularly interested in divisors. Why? Because the divisors of a number are exactly those that divide it. One thing that is of particular interest is when certain numbers share divisors. This is one way that we can relate numbers with each other.
For instance, the numbers 8 and 16 feel more “similar” to each other than 8 and 20 do, but these feel more similar than even 8 and 21. If we examine the divisors of each of these numbers, we see that 8 and 16 share many (1, 2, 4, 8), while 8 and 20 share fewer (1, 2, 4), and 8 and 21 only share 1.
From this, we may also want to explicitly consider the greatest divisor that is shared by our integers.
Let $a,b,c$ be integers. If $c \mid a$ and $c \mid b$, then $c$ is a common divisor of $a$ and $b$. The integer $d$ is the greatest common divisor of $a$ and $b$ if $|c| \leq |d|$ for all common divisors $c$ of $a$ and $b$. The greatest common divisor of $a$ and $b$ is denoted $\gcd(a,b)$.
So we have this notion of the greatest common divisor, but how does one find or compute it? The obvious way to do this is to compute all divisors of $m$ and $n$, find the common divisors, and find the largest of those. The big problem with this approach is that factoring integers is a notoriously hard problem to solve efficiently.
At first, this doesn’t seem so bad. A naive approach to computing divisors of an integer $n$ is to check each integer from $1$ to $n$. With a bit more thinking, we can shave our search down to all integers up to $\sqrt n$, or $n^{\frac 1 2}$, since we always pair “smaller” divisors with larger ones—the largest such “small” divisor will necessarily occur before the square root of $n$.
What are the divisors of 90? They are 1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, and 90. Notice they are paired in the following way: \[\begin{matrix} 1 & 2 & 3 & 5 & 6 & 9 \\ 90 & 45 & 30 &18 & 15 & 10 \end{matrix}\]
Observe also that $9 \lt \sqrt{90} \lt 10$ since $81 \lt 90 \lt 100$.
From this, we may conclude that such an algorithm runs in $O(n^{\frac 1 2})$ time, which is even better than linear time. But let’s think a bit more carefully about how we measure the efficiency of algorithms. Informally, we can think of this as the number of steps that the algorithm needs to take, and we compare this to the size of the input of the algorithm. We would like the number of steps of our algorithm to grow slowly as we give it larger and larger inputs.
But what is the size of a number? Here, the size of the number is the size of its representation. This would be the number of digits it takes to write the number down. This means that the size of a number $n$ is $d = \log n$.
Consider the number $2434$, when written in decimal. We can explicitly write this in terms of the place value of each digit as \[2434 = 2 \times 10^3 + 4 \times 10^2 + 3 \times 10^1 + 4 \times 10^0.\]
Here, the exact base doesn’t matter too much. But what this means then is that searching for divisors from 1 through $\sqrt n$ would require approximately $\sqrt n = 10^{\log \sqrt n} = 10^d$ steps, assuming your number was in decimal representation (swap with the appropriate base if desired). In other words, the number of steps we need to compute this grows exponentially as we increase the size of our number. Unfortunately, exponentially growing functions do not grow slowly.
There are some heuristics that we can apply and some tricks that we can pull, but in general we do not have a fast algorithm for factoring numbers. This fact happens to be the backbone of many public-key cryptographic systems we use today.
However, if all we care about is the greatest common divisor and not any of the other divisors, then we will see a theorem will get us there efficiently.
First, a bit of notation.
Let $n,d,q,r$ be integers that satisfy $n = d \cdot q + r$ and $0 \leq r \lt d$, as in the Division Theorem. We define the function $\mathop{\mathbf{mod}}$ by $n \mathop{\mathbf{mod}} d = r$.
You may be more familiar with $\mathop{\mathbf{mod}}$ as the modulus operator % from Python. It’s a handy way to refer to the remainder without having to say “$r$ as in the Division Theorem” every time. We can similarly define $n \mathop{\mathbf{div}} d = q$, which is analogous to the Python operator // (hence the name of the function, $\operatorname{divmod}$).
If $d = \gcd(a,b)$, $b \neq 0$, and $r = a \mathop{\mathbf{mod}} b$, then $d = \gcd(b,r)$.
This result establishes a relationship between the gcd of two integers and the gcd of the integers and the remainder that’s obtained when they are divided. This relationship gives us a way to compute the gcd: \[\gcd(a,b) = \begin{cases} a & \text{if $b = 0$,} \\ \gcd(b, a \mathop{\mathbf{mod}} b) & \text{otherwise,} \end{cases}\]
which becomes the following function fairly straightforwardly:
def euclid(a: int, b: int) -> int:
if b == 0:
return a
else:
return euclid(b, a % b)
This algorithm is called Euclid’s algorithm, named after Euclid who describes it in the Elements. Euclid is the Greek mathematician from around 300 BC who, in the Elements, describes a lot of the elementary geometry, algebra, and number theory that we learn in school. Euclid’s algorithm is considered to be one of the oldest known algorithms.
Suppose we want to compute the gcd of 232 and 72. We apply Euclid’s algorithm as follows: \begin{align*} \gcd(232,72) &= \gcd(72,16) \\ &= \gcd(16,8) \\ &= \gcd(8,0) \\ &= 8 \end{align*}
With only four steps, this is noticeably less than the $\sqrt{72} \approx 8$ iterations we’d take with the slightly improved naive algorithm. And if we try running this in Python, we’ll see that the difference becomes far more pronounced.
>>> trace_euclid(38429972, 2498232)
function a b return value called by
---------- -------- ------- -------------- -------------------------
euclid 38429972 2498232 4 N/A
euclid 2498232 956492 4 euclid(38429972, 2498232)
euclid 956492 585248 4 euclid(2498232, 956492)
euclid 585248 371244 4 euclid(956492, 585248)
euclid 371244 214004 4 euclid(585248, 371244)
euclid 214004 157240 4 euclid(371244, 214004)
euclid 157240 56764 4 euclid(214004, 157240)
euclid 56764 43712 4 euclid(157240, 56764)
euclid 43712 13052 4 euclid(56764, 43712)
euclid 13052 4556 4 euclid(43712, 13052)
euclid 4556 3940 4 euclid(13052, 4556)
euclid 3940 616 4 euclid(4556, 3940)
euclid 616 244 4 euclid(3940, 616)
euclid 244 128 4 euclid(616, 244)
euclid 128 116 4 euclid(244, 128)
euclid 116 12 4 euclid(128, 116)
euclid 12 8 4 euclid(116, 12)
euclid 8 4 4 euclid(12, 8)
euclid 4 0 4 euclid(8, 4)
In this case, our run makes 19 calls, while $\sqrt{2498232} \approx 1580$, which would be the number of iterations for our slightly improved naive algorithm.