Skip to main content \(\newcommand{\longdivision}[2]{#1\big)\!\!\overline{\;#2}}
\newcommand{\mlongdivision}[2]{\longdivision{#1}{#2}}
\renewcommand{\emptyset}{\{\}}
\newcommand{\blanksp}{\underline{\hspace{.25in}}}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\cspace}{-}
\newcommand{\Ta}{\mathtt{a}}
\newcommand{\Tb}{\mathtt{b}}
\newcommand{\Tc}{\mathtt{c}}
\newcommand{\Td}{\mathtt{d}}
\newcommand{\Te}{\mathtt{e}}
\newcommand{\Tf}{\mathtt{f}}
\newcommand{\Tg}{\mathtt{g}}
\newcommand{\Th}{\mathtt{h}}
\newcommand{\Ti}{\mathtt{i}}
\newcommand{\Tj}{\mathtt{j}}
\newcommand{\Tk}{\mathtt{k}}
\newcommand{\Tl}{\mathtt{l}}
\newcommand{\Tm}{\mathtt{m}}
\newcommand{\Tn}{\mathtt{n}}
\newcommand{\To}{\mathtt{o}}
\newcommand{\Tp}{\mathtt{p}}
\newcommand{\Tq}{\mathtt{q}}
\newcommand{\Tr}{\mathtt{r}}
\newcommand{\Ts}{\mathtt{s}}
\newcommand{\Tt}{\mathtt{t}}
\newcommand{\Tu}{\mathtt{u}}
\newcommand{\Tv}{\mathtt{v}}
\newcommand{\Tw}{\mathtt{w}}
\newcommand{\Tx}{\mathtt{x}}
\newcommand{\Ty}{\mathtt{y}}
\newcommand{\Tz}{\mathtt{z}}
\newcommand{\So}{\Tf}
\newcommand{\Sno}{\Tg}
\newcommand{\Si}{\Th}
\newcommand{\Sni}{\Tj}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\W}{\mathbb{W}}
\newcommand{\ZZ}{\Z}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\RR}{\R}
\newcommand{\F}{\mathbb{F}}
\newcommand{\A}{\mathbb{A}}
\newcommand{\abs}[1]{|#1|}
\newcommand{\fmod}{\bmod}
\newcommand{\fdiv}{\,\mathrm{div}\,}
\newcommand{\lcm}{\mathrm{lcm}}
\newcommand{\id}{\mathrm{id}}
\newcommand{\nr}[1]{\##1}
\newcommand{\gexp}[3]{#1^{#2 #3}}
\newcommand{\gexpp}[3]{\displaystyle\left(#1\right)^{#2 #3}}
\newcommand{\glog}[3]{\log_{#1}^{#3}#2}
\newcommand{\sol}[1]{{\color{blue}\textit{#1}}}
\newcommand{\gro}[1]{{\color{gray}#1}}
\newcommand{\todo}[1]{{\color{purple}TO DO: #1}}
\newcommand{\fixme}[1]{{\color{red}FIX ME: #1}}
\newcommand{\checkme}[1]{{\color{green}CHECK ME: #1}}
\newcommand{\degre}{^\circ}
\newcommand{\vect}[1]{\overrightarrow{#1}}
\newcommand{\nix}{}
\newcommand{\cox}[1]{\fcolorbox[HTML]{000000}{#1}{\phantom{M}}}
\newcommand{\tox}[1]{\texttt{\##1} \amp \cox{#1}}
\newcommand{\ttx}[1]{\texttt{\##1}}
\newcommand{\mox}[1]{\mathtt{\##1}}
\newcommand{\xx}{\mathtt{\#}}
\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\,}$}}}
\)
Section 4.1 Divisibility
We begin by introducing terminology.
Definition 4.1 .
Suppose that for integers
\(a\) and
\(b\text{,}\) there is an integer
\(q\) such that
\(a = b \cdot q\text{.}\) Then
\(b\) divides \(a\text{.}\)
By
Definition 4.1 if
\(b\) divides
\(a\text{,}\) then
\(a = b \cdot q\) for some integer
\(q\text{.}\) Then we have
\(a = b \cdot q + 0\) so that in particular
\(a \fmod b = 0\text{.}\) If
\(b\) does not divide
\(a\text{,}\) then
\(a \fmod b\ne 0\text{.}\) It follows immediately that if
\(b\) divides
\(a\) then
\(b\le a\text{.}\)
Problem 4.2 . Determine divisibility.
For the given values of \(a\) and \(b\text{,}\) determine whether or not \(b\) divides \(a\text{.}\) If \(b\) divides \(a\text{,}\) determine the integer \(q\) such that \(a = b \cdot q\text{.}\)
Solution .
In each case we consider the remainder \(a\fmod b\) of the division \(a\) and \(b\text{.}\)
We compute
\(30 \fmod 10 = 0\text{.}\) So
\(10\) divides
\(30\text{.}\) Furthermore, we have that
\(30\fdiv 10=3\) so
\(30=10\cdot 3\text{.}\)
We compute
\(2 \fmod 46 = 2\ne 0\text{.}\) So
\(46\) does not divide
\(2\text{.}\) (Be careful not to mix up
\(a\) and
\(b\) during the division or the conclusion. The order matters. It turns out that
\(2\) does divide
\(46\) since
\(46 = 2\cdot 23\text{.}\) )
We compute
\(29 \fmod 4 = 1\ne 0\text{.}\) So
\(4\) does not divide
\(29\text{.}\)
There are several other formulations for
\(b\) divides \(a\text{.}\)
Definition 4.3 .
Let \(a\) and \(b\) be integers. If \(b\) divides \(a\) we also say:
\(a\) is
divisible by
\(b\)
\(a\) is a
multiple of
\(b\)
\(b\) is a
divisor of
\(a\)
\(b\) is a
factor of
\(a\)
If a number divides two other numbers, it divides their sum.
Theorem 4.4 .
Let
\(b\) be a natural number and let
\(a\) and
\(c\) be integers. If
\(b\) divides
\(a\) and
\(b\) divides
\(c\text{,}\) then
\(b\) divides
\(a+c\text{.}\)
Proof.
As \(b\) divides \(a\text{,}\) there is an integer \(q\) such that \(a=b\cdot q\text{.}\) As \(b\) divides \(c\text{,}\) there is an integer \(s\) such that \(c=b\cdot s\text{.}\) With substitution and the distributive property we obtain
\begin{equation*}
a+c=(b\cdot q)+(b\cdot s)=b\cdot(q+s)\text{.}
\end{equation*}
Thus
\(a+c\) is a multiple of
\(b\) which means that
\(b\) divides
\(a+c\text{.}\)
Example 4.5 .
Let
\(b:=10\) and
\(a:=100\) and
\(c:=1000\text{.}\) Then
\(b\) divides
\(a\) and
\(b\) divides
\(c\text{.}\) Also
\(b\) divides
\(a+c=1100\text{.}\)
