Proof. We begin by proving that the set
$$
S=\{a-x b \mid x \text { an integer; } a-x b \geq 0\}
$$
is nonempty. To do this, it suffices to exhibit a value of $x$ making $a-x b$ nonnegative. Because the integer $b \geq 1,$ we have $|a| b \geq|a|,$ and so
$$
a-(-|a|) b=a+|a| b \geq a+|a| \geq 0
$$
For the choice $x=-|a|$, then, $a-x b$ lies in $S$. This paves the way for an application of the Well-Ordering Principle (Chapter 1 ), from which we infer that the set $S$ contains a smallest integer; call it $r$. By the definition of $S$, there exists an integer $q$ satisfying