Skip to main content
Mathematics LibreTexts

1.1: Division Algorithm

  • Page ID
  • This page is a draft and is under active development. 

    \( \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.


    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\).


    \(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.

    • Was this article helpful?