---- > [!theorem] Theorem. ([[division algorithm]]) > Let $n,d \in \zz$ with $d>0$. There exist *unique* $q,r \in \zz$ such that $n=qd+r \ \ \text{ and } \ \ 0 \leq r < d.$ ^15d3fd > [!note] Remark. > - $n \to$ "numerator"; > - $d \to$ "denominator"; > - $q \to$ "quotient; > - $r \to$ "remainder". > [!proof]- Proof. ([[division algorithm]]) > **Existence**. Define $S:=\{ n-dx : x \in \zz \text{ and } n-dx \geq 0 \}.$ Since $S \neq \emptyset$ [^1], by the [[Well Ordering Principle]] $S$ has smallest element $r=n-dx' \geq 0$. Rewriting as $n-dx' - r \geq 0$, observe $r<d$; if not we'd have that $n-d(x'+1) \geq 0$ is smaller that $r$. Now rewrite as $n=dx'+r$ and set $q:=x'$. \ **Uniqueness**. Suppose that $n=qd+r=q'd+r'$ where $q,r,q',r' \in \zz$ and $0 \leq r, r' < d$. Observe $d(q-q')=r-r'$ (hence $d$ [[divides]] $(r-r')$). \ WLOG $r' \leq r$. Since $0 \leq r,r' < d$, we have $0 \leq r-r' < d$. In turn, $|r-r'|<d$. Now substituting yields $|q-q'|<1$; since $q,q' \in \zz$ this means $q=q'$. That $r=r'$ is now easy to see. $\qedin$ ^e3ff19 [^1]: If $n \geq 0$ then $n \in S$ ($x=0$), else $n<0$ and $n-dn \in S$ ($x=-n$) since $d \geq 1$. ---- #### ----- #### References > [!backlink] > ```dataview TABLE rows.file.link as "Further Reading" FROM [[]] FLATTEN file.tags GROUP BY file.tags as Tag > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```