Skip to main content \(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}}
\newcommand{\ints}{\mathbb{Z}}
\newcommand{\posints}{\mathbb{N}}
\newcommand{\rats}{\mathbb{Q}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\complexes}{\mathbb{C}}
\newcommand{\twospace}{\mathbb{R}^2}
\newcommand{\threepace}{\mathbb{R}^3}
\newcommand{\dspace}{\mathbb{R}^d}
\newcommand{\nni}{\mathbb{N}_0}
\newcommand{\nonnegints}{\mathbb{N}_0}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\prob}{\operatorname{prob}}
\newcommand{\Prob}{\operatorname{Prob}}
\newcommand{\height}{\operatorname{height}}
\newcommand{\width}{\operatorname{width}}
\newcommand{\length}{\operatorname{length}}
\newcommand{\crit}{\operatorname{crit}}
\newcommand{\inc}{\operatorname{inc}}
\newcommand{\HP}{\mathbf{H_P}}
\newcommand{\HCP}{\mathbf{H^c_P}}
\newcommand{\GP}{\mathbf{G_P}}
\newcommand{\GQ}{\mathbf{G_Q}}
\newcommand{\AG}{\mathbf{A_G}}
\newcommand{\GCP}{\mathbf{G^c_P}}
\newcommand{\PXP}{\mathbf{P}=(X,P)}
\newcommand{\QYQ}{\mathbf{Q}=(Y,Q)}
\newcommand{\GVE}{\mathbf{G}=(V,E)}
\newcommand{\HWF}{\mathbf{H}=(W,F)}
\newcommand{\bfC}{\mathbf{C}}
\newcommand{\bfG}{\mathbf{G}}
\newcommand{\bfH}{\mathbf{H}}
\newcommand{\bfF}{\mathbf{F}}
\newcommand{\bfI}{\mathbf{I}}
\newcommand{\bfK}{\mathbf{K}}
\newcommand{\bfP}{\mathbf{P}}
\newcommand{\bfQ}{\mathbf{Q}}
\newcommand{\bfR}{\mathbf{R}}
\newcommand{\bfS}{\mathbf{S}}
\newcommand{\bfT}{\mathbf{T}}
\newcommand{\bfNP}{\mathbf{NP}}
\newcommand{\bftwo}{\mathbf{2}}
\newcommand{\cgA}{\mathcal{A}}
\newcommand{\cgB}{\mathcal{B}}
\newcommand{\cgC}{\mathcal{C}}
\newcommand{\cgD}{\mathcal{D}}
\newcommand{\cgE}{\mathcal{E}}
\newcommand{\cgF}{\mathcal{F}}
\newcommand{\cgG}{\mathcal{G}}
\newcommand{\cgM}{\mathcal{M}}
\newcommand{\cgN}{\mathcal{N}}
\newcommand{\cgP}{\mathcal{P}}
\newcommand{\cgR}{\mathcal{R}}
\newcommand{\cgS}{\mathcal{S}}
\newcommand{\bfn}{\mathbf{n}}
\newcommand{\bfm}{\mathbf{m}}
\newcommand{\bfk}{\mathbf{k}}
\newcommand{\bfs}{\mathbf{s}}
\newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}}
\newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}}
\newcommand{\surjection}{\xrightarrow[\text{onto}]{}}
\newcommand{\nin}{\not\in}
\newcommand{\prufer}{\text{prüfer}}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\stab}{stab}
\DeclareMathOperator{\var}{var}
\newcommand{\inv}{^{-1}}
\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 B.8 Multiplication as a Binary Operation
We define a binary operation \(\times\text{,}\) called multiplication , on the set of natural numbers. When \(m\) and \(n\) are natural numbers, \(m\times n\) is also called the product of \(m\) and \(n\text{,}\) and it sometimes denoted \(m*n\) and even more compactly as \(mn\text{.}\) We will use this last convention in the material to follow. Let \(n\in \nonnegints\text{.}\) We define
\(n0=0\text{,}\) and
\(n(k+1)=nk +n\text{.}\)
Note that
\(10=0\) and
\(01=00+0=0\text{.}\) Also, note that
\(11=10+1=0+1=1\text{.}\) More generally, from (ii) and
Lemma B.19 , we conclude that if
\(m,n\neq0\text{,}\) then
\(mn\neq0\text{.}\)
Theorem B.21 . Left Distributive Law.
\(m(n+p)=mn + mp\text{,}\) for all
\(m,n,p\in \nonnegints\text{.}\)
Proof.
Let \(m,n\in \nonnegints\text{.}\) Then
\begin{equation*}
m(n+0)=mn = mn +0 = mn+ m0.
\end{equation*}
Now assume \(m(n+k) = mn + mk\text{.}\) Then
\begin{align*}
m[n+(k+1)] \amp = m[(n+k)+1]=m(n+k)+m\\
\amp =(mn+mk)+m=mn+(mk+m)= mn+m(k+1).
\end{align*}
Theorem B.22 . Right Distributive Law.
\((m+n)p=mp + np\text{,}\) for all
\(m,n,p\in \nonnegints\text{.}\)
Proof.
Let \(m,n\in \nonnegints\text{.}\) Then
\begin{equation*}
(m+n)0 =0 = 0+0 = m0 + n0.
\end{equation*}
Now assume \((m+n)k = mk + nk\text{.}\) Then
\begin{align*}
(m+n)(k+1)\amp =(m+n)k+(m+n)= (mk+nk) +(m+n)\\
\amp =(mk+m)+(nk+n)=m(k+1)+n(k+1).
\end{align*}
Theorem B.23 . Associative Law of Multiplication.
\(m(np) = (mn)p\text{,}\) for all
\(m,n,p\in \nonnegints\text{.}\)
Proof.
Let \(m,n\in \nonnegints\text{.}\) Then
\begin{equation*}
m(n0)= m0 = 0 = (mn)0.
\end{equation*}
Now assume that \(m(nk)=(mn)k\text{.}\) Then
\begin{equation*}
m[n(k+1)]= m(nk + n)= m(nk) + mn =(mn)k + mn = (mn)(k+1).
\end{equation*}
The commutative law requires some preliminary work.
Lemma B.24 .
\(n0= 0n=0\text{,}\) for all
\(n\in \nonnegints\text{.}\)
Proof.
The lemma holds trivially when \(n=0\text{.}\) Assume \(k0=
0k=0\text{.}\) Then
\begin{equation*}
(k+1)0 =0 = 0+0= 0k+0=0(k+1).
\end{equation*}
Lemma B.25 .
\(n1 =1n=n\text{,}\) for every
\(n\in \nonnegints\text{.}\)
Proof.
\(01=00+0=0 =10\text{.}\) Assume \(k1=1k=k\text{.}\) Then
\begin{equation*}
(k+1)1=k1+11=1k+1=1(k+1).
\end{equation*}
Theorem B.26 . Commutative Law of Multiplication.
\(mn=nm\text{,}\) for all
\(m,n\in \nonnegints\text{.}\)
Proof.
Let \(m\in \nonnegints\text{.}\) Then \(m0=0m\text{.}\) Assume \(mk=km\text{.}\) Then
\begin{equation*}
m (k+1) = mk +m = km+m= km +1m=(k+1)m.
\end{equation*}
