# 1.1: Division Algorithm

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

In the proof of numerous theorems, we will utilize the well-ordering principle.

##### Theorem $$\PageIndex{1}$$: Well ordering principle

Every non-empty subset of $$\mathbb{N}$$ has the smallest number.

## Division Algorithm

##### Theorem $$\PageIndex{2}$$: Division Algorithm

Let $$n$$ and $$d$$ be integers. Then there exist unique integers $$q$$ and $$r$$ such that $$n=dq+r, 0\leq r <|d|$$, where $$q$$ is the quotient and $$r$$ is the remainder, and the absolute value of $$d$$ is defined as:

$|d|= \left\{ \begin{array}{c} d, \mbox{if } d \geq 0\\ \\ -d, \mbox{if } d<0. \end{array} \right.$

Proof

We will show that $$q,r \in \mathbb{Z}$$ exist and that they are unique.

Let $$a,b \in \mathbb{Z}$$ s.t. $$b>0$$.

Let $$S$$ be a set defined by  $$S=\{a-bm: a-bm \ge 0, m\in \mathbb{Z}\}$$.

We will show existence by examining the possible cases.

Case 1:  $$0 \in S$$

If $$0 \in S$$, then $$a-bm=0$$ for some $$m \in \mathbb{Z}$$.

Thus, $$a=bm$$

Since $$b|a$$, $$q=m$$ and $$r=0$$.

Therefore existence has been proved.

Case 2:  $$0 \notin S$$.

Since $$0 \notin S$$, we will show that $$S \ne \emptyset$$ by examining the possible cases.  Note: $$S \subseteq \mathbb{N}$$.

Case a:  $$a>0$$.

Since $$a>0$$, $$a=a-b(0)>0$$.

Therefore $$a \in S$$.

Case b: $$a<0$$.

Consider $$a-bm$$, where $$m=2a$$.

Thus $$a-b(2a)=a(1-2b)$$.

Consider  $$1-2b$$ is always negative since $$b>0 \cap b \in \mathbb{N}$$, thus greatest $$1-2b$$ can be in $$-1$$.

Therefore $$a(1-2b) \ge 0$$ since $$b \ge 1$$.

Note: The $$\ge$$ could be > without loss of generality.

Since both case a & b are non-empty sets, $$S \ne \emptyset \subseteq \mathbb{N}$$.

Thus $$S$$ has the smallest element by the well-ordering principle, and lets call it $$r$$.

That means $$r=a-bm$$, for some $$m\in \mathbb{Z}$$ where $$r \ge 0$$.

Thus the non-empty set is $$r=a-bm \ge 0$$.

We shall show that $$r < b$$ by proceeding with a proof by contradiction.

Assume that $$r \ge b$$.

Then $$a-b(m+1)=a-bm-b=r-b \ge 0$$ for some $$m \in \mathbb{Z}$$.

Then $$r-b \in S$$ and $$r-b<r$$. Note $$(b>0)$$

This contradicts that $$r$$ is the smallest element of $$S$$.

Therefore $$r < b$$.

Having examined all possible cases, $$a=bq+r, 0 \le r < b$$ exists.

Next, we will show uniqueness.

Let $$r_1,r_2, q_1,q_2$$ s.t. $$a=bq_1+r_1$$ and $$a=bq_2+r_2$$ with $$0 \le r_1,r_2 < b$$.

Consider $$bq_1+r_1=bq_2+r_2$$, $$0 \le r_1<b$$.

Further since $$b(q_1-q_2)=r_2-r_1$$, $$b|(r_2-r_1)}$$, but $$b$$ has to be $$\le r_1$$.

Since, $$r_2-r_1 < b$$, $$r_2-r_1=0$$ and $$r_1=r_2$$.

Hence $$q_1=q_2$$.

Therefore uniqueness has been shown.

##### Example $$\PageIndex{1}$$

Find the $$q$$ is the quotient and $$r$$ is the remainder for the following values of $$n$$ and $$d$$.

1. $$n=2018$$ and $$d=343$$.

Thus $$2018=(5)(343)+303$$.

2. $$n=-2018$$ and $$d=343$$.

Thus $$-2018=(-6)(343)+40$$.-

3, . $$n=2018$$ and $$d=-343$$.

Thus $$2018=(6)(-343)+40$$.

4.

$$n=-2018$$ and $$d=-343$$.

Thus $$-2018=(6)(-343)+ 40$$.

This page titled 1.1: Division Algorithm is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Pamini Thangarajah.