Division Algorithm: Euclids division lemme states that if a and b are any two positive integers then there exist unique integers q and r such that, $$ a = q b + r \, \, 0 \leq r < b $$
$$ \therefore $$ option C is correct.
Proof: We begin by proving that the set s = {a - xb | x is an integer: a-xb $$\geq$$ 0 }
is non-empty. To do this, if suffices to exhibit a value of x making a-xb nonnegative a value of x making a-xb 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 - xb lies in s. This paves the way for an application of well ordering principle, from which we infer that the set S contains a smallest integer : call it r. By the definition S, $$\exists$$ an integer q satisfying , r = a - qb , $$0\leq r$$
we argue that r < b. If this were not this case, then r $$\geq$$ 0 and a - ( q + 1 ) b = ( a - q b ) - b = r - b $$\geq$$ 0
This implication is that the integer a - ( q + 1 ) b has the proper form to belong to the set S. But a - ( q + 1 ) b = r - b < r , leading to a contradiction of the choice of r as the smallest member of S. Hence r < b .
Next we turn to the task of showing the uniqueness of q and r. Suppose that a has two representation of the desired form say,
$$ a = q b + r = q^{'}b + r^{'} $$
Where $$ 0 \leq r < b, \, 0 \leq r^{'} < b . $$ Then $$r^{'}- r = b (q - q^{'}) $$ and, owing to the fact that
$$ | r^{'} - r | = b | q - q^{'} | $$ upon adding two inequalities $$-b < -r \leq 0 $$ and $$ 0 \leq r^{'} < b $$ we obtain $$ -b < r^{'}-r < b \Rightarrow |r^{'} - r | < b $$
Thus, $$b|q-q^{'}| < b $$ which yields $$ 0 \leq |q-q^{'} | < 1 $$
As, $$ |q-q^{'} | $$ is positive, the only possibility is that $$ |q-q^{'} | = 0 $$ where $$q = q^{'} : $$ this is turns give $$ r = r^{'} $$ and ends the proof.