| | |
Proof:
We need to argue two things. First, we need to show that $q$ and $r$ exist. Then, we need to show that $q$ and $r$ are unique.
To show that $q$ and $r$ exist, let us play around with a specific example first to get an idea of what might be involved, and then attempt to argue the general case.
Recall that if $b$ is positive, the remainder of the division of $b$ by $a$ is the result of subtracting as many $a$'s as are possible while still keeping the result non-negative. If $b$ is negative, the remainder is found in a slightly different way -- by adding as many $a$'s as necessary until the result becomes non-negative. With this in mind, suppose $b = 27$ and $a = 5$, and let us consider the set of all integers that results from either adding to 27, or subtracting from 27, some multiple of 5: $$\{ \ldots, -8, -3, 2, 7, 12, 17, 22, 27, 32, 37, \ldots \}$$ Now let us reduce this set down to just the positive values present, to produce a set $$S = \{2, 7, 12, 22, 27, 32, 37, \ldots\}$$ We can see that the smallest element of this set (i.e., $2$) is the remainder we seek -- but in the more general case, how can we be guaranteed that this smallest element exists? Recall the well-ordering principle tells us that any non-empty set of non-negative integers contains a least element. Perhaps this could prove helpful...
Now, with a hint of what tool might prove useful, let us turn our attention to the general case, for some arbitrary $a$ and $b$, with $a > 0$. In a manner similar to that employed above, we can construct a set $$S = \{ b - ka, \textrm{ where } k \textrm{ is an integer and } b - ka \ge 0 \}$$ We seek to show using the well-ordering principle that this set has a least element (which we hope will play the role of $r$). By its construction, S is only allowed to contain non-negative integers, so it remains to show that it is non-empty.
If $b \ge 0$, this is trivial, as $b$ itself will be in the set (consider $k=0$).
If $b \lt 0$, consider $k = b$ instead. We aim to show that $b - ka \ge 0$ for this value of $k$ and must then necessarily be in the set S. To this end, note $$b - ka = b - ba = b (1-a)$$ and the factor $(1-a)$ must be either zero or negative as $a \gt 0$. Consequently $b(1-a) \ge 0$. Putting the left side of this last inequality back into its original form, we end up with $b - ka \ge 0$. Thus, we conclude $S$ must contain the element $b - ka$ when $k=b$.
So regardless of the value of $b$, $S$ will have at least one element, and is thus non-empty. Having demonstrated that the set $S$ is a non-empty set of non-negative values, the well-ordering principle applies and guarantees that $S$ has a least element.
Now the question turns to whether or not this least element really is a reasonable value for $r$, and whether it can produce some reasonable value for $q$ as well...
Suppose this least element is given by $$r = b - k_r a$$ Of course, if this is to be a reasonable value for our purposes, we will need to be assured that $0 \le r \lt a$.
We already know $r$ is non-negative as it was in $S$, so all we need to do now is assure ourselves that it is less than $a$. But consider the alternative: if $r \ge a$, then $b - k_r a \ge a$, which implies (after subtracting $a$ from both sides) that $$b - (k_r + 1)a \ge 0$$ This contradicts the fact that $r$ was the smallest element of the set $S$. So it must be the case that $r \lt a$.
Finding $q$ is now easy, as if $b = qa + r$, then $$q = \frac{b-r}{a}$$ Replacing $r$ with $b - k_r a$, we have $$q = \frac{b - (b - k_r a)}{a} = \frac{k_r a}{a} = k_r$$ Thus, there exist integer values $q$ and $r$, with $0 \le r \lt a$, such that $b = qa + r$.
It remains to show that these values for $q$ and $r$ are unique.
Effectively, we need to show that if $b = q_1 a + r_1$ and $b = q_2 a + r_2$, then it can only be the case that $q_1 = q_2$ and $r_1 = r_2$.
Without loss of generality, let us suppose that $r_2 \ge r_1$. Substituting for $b$, we have $$q_1 a + r_1 = q_2 a + r_2$$ But then $$\begin{array}{rcl} q_1 a - q_2 a &=& r_2 - r_1 \quad \textrm{and thus,}\\ r_2 - r_1 &=& a(q_1 - q_2) \end{array}$$ Consequently, $r_2 - r_1$ is some multiple of $a$.
However, since $0 \le r_1, r_2 \lt a$ and $r_2 > r_1$, it must be the case that $0 \le r_2 - r_1 \lt a$. The only multiple of $a$ in this range is zero, so $r_2 - r_1 = 0$, or equivalently, $r_1 = r_2$.
Further, as seen before, $$q_2 = \frac{b - r_2}{a} \quad \textrm{and} \quad q_1 = \frac{b - r_1}{a}$$ Since $r_1$ and $r_2$ agree in value, this forces $q_1$ and $q_2$ to agree in value as well.
Thus, having shown that if $b = q_1 a + r_1$ and $b = q_2 a + r_2$, then it can only be the case that both $q_1 = q_2$ and $r_1 = r_2$, we can conclude that if there exist integers $q$ and $r$ such that $b = qa + r$ with $0 \le r \lt a$, then those values of $q$ and $r$ are unique.
Since the first part of our argument established the existence of these integers $q$ and $r$, we are done. It is indeed the case that given integers $a$ and $b$, with $a > 0$, there exist unique integers $q$ and $r$ such that $b = qa + r$ and $0 \le r \lt a$.
QED.