Integer Division

Skip to main content

\(\newcommand{\im}{{\mathrm{im}}} \newcommand{\given}{{\, :\,}} \newcommand{\hanoi}{\mathrm{hanoi}} \newcommand{\lcm}{{\mathrm{lcm}}} \newcommand{\ID}{{\mathrm{ID}}} \newcommand{\chr}{{\mathtt{chr}}} \newcommand{\ord}{{\mathtt{ord}}} \newcommand{\set}[1]{\left\lbrace #1 \right\rbrace} \newcommand{\seq}[2]{( #1 )_{#2}} \newcommand{\gr}[1]{\left( #1 \right)} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\size}[1]{\# #1} \newcommand{\id}[1]{\mathrm{id}_{#1}} \newcommand{\ip}[1]{\left\langle #1 \right\rangle} \newcommand{\floor}[1]{\left\lfloor #1\right\rfloor} \newcommand{\ceiling}[1]{\left\lceil #1\right\rceil} \newcommand{\indemph}[1]{{\textbf{\emph{#1}}\index{#1}}} \renewcommand{\implies}{\to} \renewcommand{\iff}{\leftrightarrow} \newcommand{\lxor}{\oplus} \newcommand{\cP}{\wp} \newcommand{\pset}{\cP} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\NN}{\mathbb{N}} \newcommand{\CC}{\mathbb{C}} \newcommand{\RR}{\mathbb{R}} \newcommand{\barr}[1]{\overline{#1}} \newcommand{\sage}{\textsc{Sage}} \newcommand{\magma}{\textsc{Magma}} \newcommand{\bob}{\text{Bob}} \newcommand{\true}{\text{T}} \newcommand{\false}{\text{F}} \newcommand{\ahat}{\hat{a}} \newcommand{\ah}{\ahat} \newcommand{\bhat}{\hat{b}} \newcommand{\abar}{\bar{a}} \newcommand{\cA}{\mathcal{A}} \newcommand{\cF}{\mathcal{F}} \newcommand{\cW}{\mathcal{W}} \newcommand{\todo}[1]{{\color{red} TODO: #1}} \renewcommand{\div}{\operatorname{div}} \newcommand{\gexp}[3]{#1^{#2 #3}} \newcommand{\gexpp}[3]{\displaystyle\left(#1\right)^{#2 #3}} \newcommand{\glog}[3]{\log_{#1}^{#3}#2} \def\dbend{{!!!}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)

Subsection 0.1.5 Integer Division

Multiplication of two natural number can be viewed as repeated addition. In particular, when \(n\in\NN\) and \(b\in\ZZ\) we have

\begin{equation*} n \cdot b =\underbrace{b+b+\ldots+b}_{n \text{ copies of }b}. \end{equation*}

Dividing a natural number \(a\) by a natural number \(b\) answers the question

How often does \(b\) go into \(a\) ?
🔗

🔗

We can answer this question by starting with \(a\) and repeatedly subtracting \(b\) until we obtain a number less than \(b\text{.}\) We call the number of times \(q\) that we have subtracted \(b\) the quotient of the division of \(a\) by \(b\) and the value \(r\) with \(0\le r\lt b\) that is left over the remainder. We get

\begin{equation*} a\underbrace{-b-b-\ldots-b}_{q \text{ copies of }b}=a-q\cdot b=r\lt b. \end{equation*}

If we rearrange this we get:

\begin{equation*} a=\underbrace{b+b+\ldots+b}_{q \text{ copies of }b}+r=q\cdot b+r. \end{equation*}

The above proves a theorem called Division Algorithm for non-negative integers, see Theorem 5.1.1.9 for the general version.

Theorem 0.1.5.1.

Let \(a\in\NN\) and \(b\in\NN\text{.}\) Then there are unique \(q\in\NN_0\) and \(r\in\NN_0\) such that

\begin{equation*} a=b\cdot q+r \text{ and } 0\le r\lt b. \end{equation*}

We write \(q=a \div b\) and \(r=a \bmod b\text{.}\)

We cover integer division greater detail in Divisibility.

[The transcript has both formatted text for visuals and a description at the start of the line.] [Underlined text:] Division notation [A [Division sign] B is above, B [Long division symbol] A is below. They are connected by a close brace.] [Label on the right:] Schoolchild A/B [Label:] Software engineer [A/B except the A is slightly above and the B is slightly below, and the slash is more diagonal to fit them.] A⁄B [Label:] Normal person or Unicode enthusiast [A fraction with A on the top and B on the bottom.] [Label:] Scientist [AB with -1 in superscript.] [Label:] Fancy scientist F(A, B) [text gets smaller] such that [text gets smaller] F(G)= [Text is too small to read] [Label:] Oh no, run — Figure 0.1.5.2. Division Notation. (https://xkcd.com/2687) Science tip: Scientists hardly ever use the two-dot division sign, and when they do it often doesn’t even mean division, but they still get REALLY mad when you repurpose it to write stuff like SALE! ALL SHOES 30÷ OFF!
🔗