> [!NOTE] Theorem (Division with Remainder/ Positive Divisor) > Let $a\in \mathbb{Z}$ be an [[Integers|integer]] and $b\in \mathbb{N}^{+}$ a positive [[Natural Numbers|natural number]], then $\exists!r,q\in\mathbb{Z}$ so that $a=bq+r$where $0\leq r<b.$ I.e. divide $a$ by $b$ gives $q$ times $a$ plus remainder $r.$ *Proof of existence by induction*: Fix $b\in \mathbb{N}^{+}.$ For $a\in \mathbb{N},$ let $P(a)$ be the proposition: there exists $q$ and $r$ such that $a=qb+r$ where $0\leq r<b.$ $P(0)$ is true since we can choose $q=r=0<b.$ Now suppose $P(k)$ is true so that there exists $q$ and $0\leq r <b$ so that $k=qb+r.$ Consider $k+1=qb+r+1.$ Either $r+1=b$ or $r+1<b.$ In the first case take $k+1=(q+1)b+0$ and in the second $k+1=qb+(r+1).$ So $P(k+1)$ is true. Hence by induction it is true for all $a\in \mathbb{N}^{+}.$ Thus by [[Induction Principle|mathematical induction]], for all positive divisors $b\in \mathbb{N}^{+}$ and $a\in \mathbb{N},$ $P(a)$ is true. If $a\in \mathbb{Z}^{-},$ then there exists $q,r$ so that $-a=qb+r$ with $b<r\leq 0.$ Then $a=-qb-r+b-b=b(-q-1)+(b-r)$ with $0 \leq b-r\leq b.$ If $b-r =b$ then $a=-qb$ so the statement is true. *Proof of existence using well-ordering:* Consider the set $S=\{ a-bs \mid s\ \in \mathbb{Z} \text{ and }a-sb \geq 0 \}.$ If $a<0,$ then $a-ab=a(1-b) \geq 0$ hence $a-ab\in S.$ Else if $a\geq 0$ then $a-0\cdot b=a \geq 0 ,$ hence $a\in S.$ Either way, $S$ is non-empty so by [[Well-Ordering Principle|WO]], $S$ has a unique least element that we denote $r=a-bq\geq 0.$ Additionally, $r-b=a-(q+1)b<0,$ hence $0\leq r<b.$ *Proof of uniqueness*: Suppose that there are two other integer $u,v$ such that $a=bu+v$ with $0\leq v<b.$ If $u<q,$ since $u$ and $q$ are integers we have $u+q\leq q.$ Thus $r=a-bq\leq a-b(u+1)=(a-ub)-b=v-b<0,$ contradicting the fact hat $r$ is nonnegative. A similar contradiction arises if we assume $u>q.$ Hence, by trichotomy $u=q.$ Thus, $a=bq+r=bq+v \implies v=r,$ and the uniqueness of $q$ and $r$ is established. # Applications **Congruence**: Two integers are [[Congruence Modulo n|congruent]] modulo $n$ iff they have the same remainder after division by $n.$ **GCD**: The [[Euclid's Algorithm|Euclidean algorithm]] allows use two compute the gcd of two numbers using repeated division with remainder. **Generalisations**: [[Division with Remainder Theorem for Ring of Polynomial Forms over Fields]].