<center> <img src = "https://i.imgsafe.org/52/52d2d0e4b0.jpeg" /></center>

([Image Source Link](https://pixabay.com/en/athletic-field-ground-lane-lines-1867053/), CC0 license)

We all know how to obtain quotients and remainder using the division algorithm for integers. But why is it always possible to have a __unique pair__ of quotient and remainder? This stems from the well ordering principle. 

## Well Ordering Principle

The precise proof of existence and uniqueness of quotient and remainder in the division algorithm heavily relies on well ordering principle. Well ordering principle comes from axiomatic set theory, so to make long story short, it states that any non-empty subset of natural numbers (= non-negative integers) contains a least element. 

---
___Well Ordering Principle.___ Every nonempty subset <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;S&space;\subseteq&space;\mathbb{N}" title="S \subseteq \mathbb{N}" align = "center"/>  contains an integer <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a&space;\in&space;S" title="a \in S" /> such that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a&space;\leq&space;b" title="a \leq b" /> for all <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" />'s  belonging to <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;S" title="S" /> . 

---

In fact, there are several ways to construct Natural numbers. If you follow [Peano arithmetic](https://en.wikipedia.org/wiki/Peano_axioms), then Well ordering principle is a direct consequence of principle of mathematical induction. On the other hand, if you follow [axiomatic set  theory](https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory); natural numbers are the smallest inductive set, then well ordering principle becomes trivial by construction itself.  In either case, it is a fundamental fact, so do not try to find counterexamples...

## Well known Division algorithm

The integer division algorithm can be summarized as follows. 

---
___Integer Division Algorithm.___ Given two integers <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a,b" title="a,b" align = "center"/>, with <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b \neq 0" title="q=-9,\ r=1" align ="center"/>, there exist __unique integers__ <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;q" title="q" align = "center"/> and <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r" title="r" /> satisfying 

- <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a&space;=&space;qb&space;&plus;&space;r" title="a = qb + r" align = "center"/> with 

- <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;0&space;\leq&space;r&space;<&space;|b|" title="0 \leq r < |b|" align = "center"/>

- We call <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;q" title="q" align = "center"/> as the quotient, <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r" title="r" /> as the remainder. 

---

For example, for two integers <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;37" title="37" /> and <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;8" title="8" />, we have relation 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;37=4\times&space;8&plus;5" title="37=4\times 8+5" /> </center>

so that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;q=4,&space;r=5" title="q=4, r=5" align = "center"/> . Another example involving negative integers would be <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a=-37,&space;b=-4" title="a=-37, b=-4" align = 'center'/>, then the relation becomes 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;-37=10&space;\times&space;(-4)&space;&plus;&space;3" title="-37=(-9) \times (-4) + 1" /> </center>

so that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;q=10,\&space;r=3" title="q=-9,\ r=1" align = "center"/> . We can clearly  see that in integer division algorithm, quotient and remainder is unique. 

## Why do they exist?

Well ordering principle can give us a lot of help in proving existence. For given two integers <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a,b" title="a,b" align = "center"/> with <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b\neq0" title="q=-9,\ r=1" align = "center"/>, construct a subset of natural numbers 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;S=&space;\left\{&space;a&space;-&space;xb&space;:&space;x&space;\text{&space;is&space;an&space;integer&space;and&space;}&space;a-xb&space;\geq&space;0&space;\right\}" title="S= \left\{ a - xb : x \text{ is an integer and } a-xb \geq 0 \right\}" /> </center>

In order to use well ordering principle, we must show that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;S" title="S" /> is nonempty. If <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" /> is positive, we need some negative integer <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x" title="x" /> satisfying <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a-xb&space;\geq&space;0" title="a-xb \geq 0" align = "center"/> . A good guess would be <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;-|a|" title="-|a|" align = "center"/>. In fact, 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a-(-|a|)b&space;=&space;a&space;&plus;&space;|a|b&space;\geq&space;a&space;&plus;&space;|a|&space;\geq&space;0" title="a-(-|a|)b = a + |a|b \geq a + |a| \geq 0" /> </center>

makes <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;S" title="S" /> nonempty. Also, if  <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" /> is negative, <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;|a|" title="|a|" align = "center"/> will give us a desired result. Either case S is nonempty, so the set <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;S" title="S" /> contains a smllest element, namely <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r" title="r" /> using well ordering principle. By definition of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;S" title="S" /> , there exist an integer <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;q" title="q" align = "center"/> such that 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a-qb&space;=&space;r&space;\iff&space;a&space;=&space;qb&space;&plus;&space;r" title="a-qb = r \iff a = qb + r" />  </center>

Are we done? Not yet. We must show that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r&space;<&space;|b|" title="r < |b|" align = "center"/> . Here we use the method of contradiction assuming <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r&space;\geq&space;|b|" title="r \geq |b|" align = "center"/>. 

- Assume <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b&space;>&space;0" title="b > 0" />. Then <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a&space;-&space;(q&plus;1)b&space;=&space;r&space;-&space;b&space;\geq&space;0" title="a - (q+1)b = r - b \geq 0" align = "center"/> so that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r-b&space;\in&space;S" title="r-b \in S" />. However, this contradicts to the choice of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r" title="r" /> as the smallest element of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;S" title="S" /> . 

- Assume <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b&space;<&space;0" title="b < 0" />. Then 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a&space;-&space;(q-1)b&space;=&space;r&plus;b&space;\geq&space;|b|&plus;b&space;\geq&space;0" title="a - (q-1)b = r+b \geq |b|+b \geq 0" /> </center>

so that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r&space;&plus;&space;b&space;\in&space;S" title="r + b \in S" />. Again this leads to contradiction. Thus <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r&space;<&space;|b|" title="r < |b|" align = "center"/> .  

## Why are they unique?

Technically, showing uniqueness is easy. Suppose there are two different pairs of quotient and remiander. 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a&space;=&space;q_1b&space;&plus;&space;r_1&space;=&space;q_2b&space;&plus;&space;r_2" title="a = q_1b + r_1 = q_2b + r_2" /> </center>

. Then 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r_1&space;-&space;r_2&space;=&space;b(q_2&space;-&space;q_1)&space;\implies&space;|r_1&space;-&space;r_2|&space;=&space;|b|&space;\cdot&space;|q_2&space;-&space;q_1|" title="r_1 - r_2 = b(q_2 - q_1) \implies |r_1 - r_2| = |b| \cdot |q_2 - q_1|" /> </center>

Since both <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r_1,&space;r_2" title="r_1, r_2" align = "center" /> satisfy <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;0&space;\leq&space;r_i&space;<&space;|b|" title="0 \leq r_i < |b|" align = "center"/>, the difference should be less than <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;|b|" title="|b|" align = "center"/> . Therefore, <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;|r_1&space;-&space;r_2|&space;=&space;|b|&space;\cdot&space;|q_1&space;-&space;q_2|&space;<&space;|b|" title="|r_1 - r_2| = |b| \cdot |q_1 - q_2| < |b|" align = "center"/> leads to 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;|q_1&space;-&space;q_2|&space;<&space;1" title="|q_1 - q_2| < 1" /> </center>

Because <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;q_1&space;-&space;q_2" title="q_1 - q_2" align ="center"/> is an integer, the only possibility is <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;q_1&space;-&space;q_2&space;=&space;0" title="q_1 - q_2 = 0" align = "center"/> , whence <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;q_1&space;=&space;q_2" title="q_1 = q_2" align  = "center"/> . From this, we get <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r_1&space;=&space;r_2" title="r_1 = r_2" align = "center"/>, ending the proof of uniqueness. 

## Extension to any real number

The division algorithm of integers can be easily extended to division involving two real numbers. For two real numbers <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x,&space;y" title="x, y" align = "center"/> with <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;y&space;\neq&space;0" title="y \neq 0" align = "center"/> , there always exist a quotient <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;q" title="q" align = "center"/> and remainder <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r" title="r" /> such that 

- <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x=&space;qy&space;&plus;&space;r" title="x= qy + r" align = "center"/>

- <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;0&space;\leq&space;r&space;<&space;|y|" title="0 \leq r < |y|" align = "center"/>

Note that quotient is an integer but remainder isn't. 

---

If we fix a nonzero real number <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;y" title="y" align = "center"/> as 1, then we can partition the set of real numbers by equivalence classes 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;[x]&space;=&space;\left\{&space;s&space;\in&space;\mathbb{R}&space;:&space;x&space;\text{&space;and&space;}s&space;\text{&space;have&space;same&space;remainder}&space;\right\}" title="[x] = \left\{ s \in \mathbb{R} : x \text{ and }s \text{ have same remainder} \right\}" /> </center>

This is equivalent to saying that any equivalence class has 1-1 correspondance with unit interval <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;[0,&space;1)" title="[0, 1)" align = "center"/> by 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;[x]&space;\mapsto&space;r_x,\&space;(r_x&space;\text{&space;is&space;remainder&space;when&space;divided&space;by&space;1})" title="[x] \mapsto t,\ (t \text{ is remainder when divided by 1})" /> </center>

If you are familiar with quotient groups, what we've constructed is a quotient group 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\mathbb{R}/\mathbb{Z}" title="\mathbb{R}/\mathbb{Z}" /> </center>

. With a continuous function <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;f(r_x)&space;=&space;(\cos(2\pi&space;r_x),&space;\sin(2\pi&space;r_x))" title="f(r_x) = (\cos(2\pi r_x), \sin(2\pi r_x))" align = "center"/> defined on unit interval [0, 1), this group can be viewed as a __unit circle__ on a 2D plane. 

<center> <img src = "https://i.imgsafe.org/53/53023c6eb2.png" /></center>


## Conclusion

- Well Ordering principle helps us to prove the existence of quotient and remainder in integer division algorithm.

- In fact, quotient and remainder are unique.

- We can extend this division algorithm to real numbers. Furthermore, each equivalence class of remainder corresponds to unique point in unit interval [0, 1). 

- This can be viewed as another way of representing unit circle. 

## Notable sources

- Elementary number theory - David M.Burton Chapter 2, Section 1.

---

<center> <img src = "https://media.discordapp.net/attachments/453577536413237258/477155905461551111/logo.png?width=270&height=270"/></center>

<center> <img src = "https://steemitimages.com/DQmWy4Kn1oiix2iq2Wdfc6pZ81sCq7UkfDv1U3FsNxkYao6/gear2.gif"/></center>