Like many things in life, there are many little things in mathematics that we take for granted. We hardly take a moment to look at them, see the beauty that they contain and that they create. The Division Algorithm, I think, is one of those beautiful little pieces in mathematics that deserves to be mentioned.
Let $a$ and $b$ be integers with $b > 0$. Then there exist unique integers $q$ and $r$ such that $$a = bq + r$$ where $0 \leq r < b$
This is so simple and obvious that we never bothered why is it even true.
Existence of $q$ and $r$
We deal with the uniqueness later on. Let
$$S = { a - bk : k \in Z, a - b \geq 0 }$$ Now if $0 \in S$ then $ a-bk = 0$ and thus $a = bk \Rightarrow r=0$.
But if $0 \notin S$ then we first show $S$ is non-empty. If $a$ is positive, $a-b.0 = a \in S$. If $a$ is negative, $a - b(2a) = a(1-2b) \in S$. We see that $S$ is non-empty either ways.
Let's recall Well ordering principle which states Every non-empty set of natural numbers contains a minimum element, that is, it is well ordered.
Following the principle, $S$ must have a minimum element, say $r$. Let, $r = a - bq \Rightarrow a = bq + r$, $r \geq 0$.
We now show $r < b$. Suppose $r > b$ then, $r-b = a - bq - b = a - b(q + 1)$ which is of the form $a -bk$. Thus, $r-b \in S$ and obviously $r-b < r$.
But, this contradicts with the fact that r is the smallest in $S$, led by our assumption $r > b$. Thus, $r < b$. This proves the existence of $r$ and $q$ such that $a = bq + r, 0\leq r < b$.
Uniqueness of $q$ and $r$
Suppose we have another pair $q'$ and $r'$ such that $a=bq' + r', 0 \leq r' < b$. Then, $$bq + r = bq' + r' \Rightarrow b(q - q') = r -r'$$ Let $r>r'$ then we have $b$ dividing $r-r'$ but, $$0 \leq r-r' \leq r < b$$ This is possible only if $r-r'=0$. Thus, $r'=r$ and $q'=q$.
Conclusion
The seemingly can-be-taken-for-granted statement involves pretty beautiful and not very straightforward proof. So much to learn from mathematics! I hope this was an interesting read.
NOTE: The proof comes from Abstract Algebra Theory and Applications