Remainders and divisibility

\( \newcommand{\andeq}{\text{\qquad and\qquad}} \newcommand{\respectively}[1]{\text{\qquad(respectively,\quad}{#1}\text{\quad)}} \newcommand{\resp}[1]{\text{\qquad(resp.,\quad}{#1}\text{\quad)}} \newcommand{\comma}{\rlap{\ ,}} \newcommand{\period}{\rlap{\ .}} \newcommand{\semicolon}{\rlap{\ ;}} \newcommand{\mathup}[1]{\mathrm{#1}} \newcommand{\mathbfup}[1]{\mathbf{#1}} \renewcommand{\AA}{\mathbfit{A}} \newcommand{\BB}{\mathbfit{B}} \newcommand{\CC}{\mathbfit{C}} \newcommand{\DD}{\mathbfit{D}} \newcommand{\EE}{\mathbfit{E}} \newcommand{\FF}{\mathbfit{F}} \newcommand{\GG}{\mathbfit{G}} \newcommand{\HH}{\mathbfit{H}} \newcommand{\II}{\mathbfit{I}} \newcommand{\JJ}{\mathbfit{J}} \newcommand{\KK}{\mathbfit{K}} \newcommand{\LL}{\mathbfit{L}} \newcommand{\MM}{\mathbfit{M}} \newcommand{\NN}{\mathbfit{N}} \newcommand{\OO}{\mathbfit{O}} \newcommand{\PP}{\mathbfit{P}} \newcommand{\QQ}{\mathbfit{Q}} \newcommand{\RR}{\mathbfit{R}} \renewcommand{\SS}{\mathbfit{S}} \newcommand{\TT}{\mathbfit{T}} \newcommand{\UU}{\mathbfit{U}} \newcommand{\VV}{\mathbfit{V}} \newcommand{\WW}{\mathbfit{W}} \newcommand{\XX}{\mathbfit{X}} \newcommand{\YY}{\mathbfit{Y}} \newcommand{\ZZ}{\mathbfit{Z}} \let\Gammaup\Gamma \let\Deltaup\Delta \let\Thetaup\Theta \let\Lambdaup\Lambda \let\Xiup\Xi \let\Piup\Pi \let\Sigmaup\Sigma \let\Upsilonup\Upsilon \let\Phiup\Phi \let\Psiup\Psi \let\Omegaup\Omega \renewcommand{\Gamma}{\mathit{\Gammaup}} \renewcommand{\Delta}{\mathit{\Deltaup}} \renewcommand{\Theta}{\mathit{\Thetaup}} \renewcommand{\Lambda}{\mathit{\Lambdaup}} \renewcommand{\Xi}{\mathit{\Xiup}} \renewcommand{\Pi}{\mathit{\Piup}} \renewcommand{\Sigma}{\mathit{\Sigmaup}} \renewcommand{\Upsilon}{\mathit{\Upsilonup}} \renewcommand{\Phi}{\mathit{\Phiup}} \renewcommand{\Psi}{\mathit{\Psiup}} \renewcommand{\Omega}{\mathit{\Omegaup}} \renewcommand{\epsilon}{\varepsilon} \newcommand{\el}{\ell} \renewcommand{\phi}{\varphi} \newcommand{\mfa}{\mathfrak{a}} \newcommand{\mfb}{\mathfrak{b}} \newcommand{\mfc}{\mathfrak{c}} \newcommand{\mfd}{\mathfrak{d}} \newcommand{\mfe}{\mathfrak{e}} \newcommand{\mff}{\mathfrak{f}} \newcommand{\mfg}{\mathfrak{g}} \newcommand{\mfh}{\mathfrak{h}} \newcommand{\mfi}{\mathfrak{i}} \newcommand{\mfj}{\mathfrak{j}} \newcommand{\mfk}{\mathfrak{k}} \newcommand{\mfl}{\mathfrak{l}} \newcommand{\mfm}{\mathfrak{m}} \newcommand{\mfn}{\mathfrak{n}} \newcommand{\mfo}{\mathfrak{o}} \newcommand{\mfp}{\mathfrak{p}} \newcommand{\mfq}{\mathfrak{q}} \newcommand{\mfr}{\mathfrak{r}} \newcommand{\mfs}{\mathfrak{s}} \newcommand{\mft}{\mathfrak{t}} \newcommand{\mfu}{\mathfrak{u}} \newcommand{\mfv}{\mathfrak{v}} \newcommand{\mfw}{\mathfrak{w}} \newcommand{\mfx}{\mathfrak{x}} \newcommand{\mfy}{\mathfrak{y}} \newcommand{\mfz}{\mathfrak{z}} \newcommand{\ahat}{\hat{a}} \newcommand{\bhat}{\hat{b}} \newcommand{\chat}{\hat{c}} \newcommand{\dhat}{\hat{d}} \newcommand{\ehat}{\hat{e}} \newcommand{\fhat}{\hat{f}} \newcommand{\ghat}{\hat{g}} \newcommand{\hhat}{\hat{h}} \newcommand{\ihat}{\hat{\i}} \newcommand{\jhat}{\hat{\j}} \newcommand{\khat}{\hat{k}} \newcommand{\elhat}{\hat{\el}} \newcommand{\mhat}{\hat{m}} \newcommand{\nhat}{\hat{n}} \newcommand{\ohat}{\hat{o}} \newcommand{\phat}{\hat{p}} \newcommand{\qhat}{\hat{q}} \newcommand{\rhat}{\hat{r}} \newcommand{\shat}{\hat{s}} \newcommand{\that}{\hat{t}} \newcommand{\uhat}{\hat{u}} \newcommand{\vhat}{\hat{v}} \newcommand{\what}{\hat{w}} \newcommand{\xhat}{\hat{x}} \newcommand{\yhat}{\hat{y}} \newcommand{\zhat}{\hat{z}} \newcommand{\alphahat}{\hat{\alpha}} \newcommand{\betahat}{\hat{\beta}} \newcommand{\gammahat}{\hat{\gamma}} \newcommand{\deltahat}{\hat{\delta}} \newcommand{\epsilonhat}{\hat{\epsilon}} \newcommand{\zetahat}{\hat{\zeta}} \newcommand{\etahat}{\hat{\eta}} \newcommand{\thetahat}{\hat{\theta}} \newcommand{\iotahat}{\hat{\iota}} \newcommand{\kappahat}{\hat{\kappa}} \newcommand{\lambdahat}{\hat{\lambda}} \newcommand{\muhat}{\hat{\mu}} \newcommand{\nuhat}{\hat{\nu}} \newcommand{\xihat}{\hat{\xi}} \newcommand{\pihat}{\hat{\pi}} \newcommand{\rhohat}{\hat{\rho}} \newcommand{\sigmahat}{\hat{\sigma}} \newcommand{\tauhat}{\hat{\tau}} \newcommand{\upsilonhat}{\hat{\upsilon}} \newcommand{\phihat}{\hat{\phi}} \newcommand{\chihat}{\hat{\chi}} \newcommand{\psihat}{\hat{\psi}} \newcommand{\omegahat}{\hat{\omega}} \newcommand{\Ahat}{\hat{A}} \newcommand{\Bhat}{\hat{B}} \newcommand{\Chat}{\hat{C}} \newcommand{\Dhat}{\hat{D}} \newcommand{\Ehat}{\hat{E}} \newcommand{\Fhat}{\hat{F}} \newcommand{\Ghat}{\hat{G}} \newcommand{\Hhat}{\hat{H}} \newcommand{\Ihat}{\hat{I}} \newcommand{\Jhat}{\hat{J}} \newcommand{\Khat}{\hat{K}} \newcommand{\Lhat}{\hat{L}} \newcommand{\Mhat}{\hat{M}} \newcommand{\Nhat}{\hat{N}} \newcommand{\Ohat}{\hat{O}} \newcommand{\Phat}{\hat{P}} \newcommand{\Qhat}{\hat{Q}} \newcommand{\Rhat}{\hat{R}} \newcommand{\Shat}{\hat{S}} \newcommand{\That}{\hat{T}} \newcommand{\Uhat}{\hat{U}} \newcommand{\Vhat}{\hat{V}} \newcommand{\What}{\hat{W}} \newcommand{\Xhat}{\hat{X}} \newcommand{\Yhat}{\hat{Y}} \newcommand{\Zhat}{\hat{Z}} \newcommand{\Gammahat}{\hat{\Gamma}} \newcommand{\Deltahat}{\hat{\Delta}} \newcommand{\Thetahat}{\hat{\Theta}} \newcommand{\Lambdahat}{\hat{\Lambda}} \newcommand{\Xihat}{\hat{\Xi}} \newcommand{\Pihat}{\hat{\Pi}} \newcommand{\Sigmahat}{\hat{\Sigma}} \newcommand{\Upsilonhat}{\hat{\Upsilon}} \newcommand{\Phihat}{\hat{\Phi}} \newcommand{\Chihat}{\hat{\Chi}} \newcommand{\Psihat}{\hat{\Psi}} \newcommand{\Omegahat}{\hat{\Omega}} \newcommand{\atilde}{\tilde{a}} \newcommand{\btilde}{\tilde{b}} \newcommand{\ctilde}{\tilde{c}} \newcommand{\dtilde}{\tilde{d}} \newcommand{\etilde}{\tilde{e}} \newcommand{\ftilde}{\tilde{f}} \newcommand{\gtilde}{\tilde{g}} \newcommand{\htilde}{\tilde{h}} \newcommand{\itilde}{\tilde{\i}} \newcommand{\jtilde}{\tilde{\j}} \newcommand{\ktilde}{\tilde{k}} \newcommand{\eltilde}{\tilde{\el}} \newcommand{\mtilde}{\tilde{m}} \newcommand{\ntilde}{\tilde{n}} \newcommand{\otilde}{\tilde{o}} \newcommand{\ptilde}{\tilde{p}} \newcommand{\qtilde}{\tilde{q}} \newcommand{\rtilde}{\tilde{r}} \newcommand{\stilde}{\tilde{s}} \newcommand{\ttilde}{\tilde{t}} \newcommand{\utilde}{\tilde{u}} \newcommand{\vtilde}{\tilde{v}} \newcommand{\wtilde}{\tilde{w}} \newcommand{\xtilde}{\tilde{x}} \newcommand{\ytilde}{\tilde{y}} \newcommand{\ztilde}{\tilde{z}} \newcommand{\alphatilde}{\tilde{\alpha}} \newcommand{\betatilde}{\tilde{\beta}} \newcommand{\gammatilde}{\tilde{\gamma}} \newcommand{\deltatilde}{\tilde{\delta}} \newcommand{\epsilontilde}{\tilde{\epsilon}} \newcommand{\zetatilde}{\tilde{\zeta}} \newcommand{\etatilde}{\tilde{\eta}} \newcommand{\thetatilde}{\tilde{\theta}} \newcommand{\iotatilde}{\tilde{\iota}} \newcommand{\kappatilde}{\tilde{\kappa}} \newcommand{\lambdatilde}{\tilde{\lambda}} \newcommand{\mutilde}{\tilde{\mu}} \newcommand{\nutilde}{\tilde{\nu}} \newcommand{\xitilde}{\tilde{\xi}} \newcommand{\pitilde}{\tilde{\pi}} \newcommand{\rhotilde}{\tilde{\rho}} \newcommand{\sigmatilde}{\tilde{\sigma}} \newcommand{\tautilde}{\tilde{\tau}} \newcommand{\upsilontilde}{\tilde{\upsilon}} \newcommand{\phitilde}{\tilde{\phi}} \newcommand{\chitilde}{\tilde{\chi}} \newcommand{\psitilde}{\tilde{\psi}} \newcommand{\omegatilde}{\tilde{\omega}} \newcommand{\Atilde}{\widetilde{A}} \newcommand{\Btilde}{\widetilde{B}} \newcommand{\Ctilde}{\widetilde{C}} \newcommand{\Dtilde}{\widetilde{D}} \newcommand{\Etilde}{\widetilde{E}} \newcommand{\Ftilde}{\widetilde{F}} \newcommand{\Gtilde}{\widetilde{G}} \newcommand{\Htilde}{\widetilde{H}} \newcommand{\Itilde}{\widetilde{I}} \newcommand{\Jtilde}{\widetilde{J}} \newcommand{\Ktilde}{\widetilde{K}} \newcommand{\Ltilde}{\widetilde{L}} \newcommand{\Mtilde}{\widetilde{M}} \newcommand{\Ntilde}{\widetilde{N}} \newcommand{\Otilde}{\widetilde{O}} \newcommand{\Ptilde}{\widetilde{P}} \newcommand{\Qtilde}{\widetilde{Q}} \newcommand{\Rtilde}{\widetilde{R}} \newcommand{\Stilde}{\widetilde{S}} \newcommand{\Ttilde}{\widetilde{T}} \newcommand{\Utilde}{\widetilde{U}} \newcommand{\Vtilde}{\widetilde{V}} \newcommand{\Wtilde}{\widetilde{W}} \newcommand{\Xtilde}{\widetilde{X}} \newcommand{\Ytilde}{\widetilde{Y}} \newcommand{\Ztilde}{\widetilde{Z}} \newcommand{\Gammatilde}{\widetilde{\Gamma}} \newcommand{\Deltatilde}{\widetilde{\Delta}} \newcommand{\Thetatilde}{\widetilde{\Theta}} \newcommand{\Lambdatilde}{\widetilde{\Lambda}} \newcommand{\Xitilde}{\widetilde{\Xi}} \newcommand{\Pitilde}{\widetilde{\Pi}} \newcommand{\Sigmatilde}{\widetilde{\Sigma}} \newcommand{\Upsilontilde}{\widetilde{\Upsilon}} \newcommand{\Phitilde}{\widetilde{\Phi}} \newcommand{\Chitilde}{\widetilde{\Chi}} \newcommand{\Psitilde}{\widetilde{\Psi}} \newcommand{\Omegatilde}{\widetilde{\Omega}} \DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\End}{End} \DeclareMathOperator{\Equival}{Equiv} \DeclareMathOperator{\Fun}{Fun} \newcommand{\Funcross}{\Fun^{\cross}} \newcommand{\Functs}{\Fun^{\cts}} \newcommand{\Funpyk}{\Functs} \newcommand{\Funlowerstar}{\Fun_{\ast}} \newcommand{\Funupperstar}{\Fun^{\ast}} \DeclareMathOperator{\Hom}{Hom} \newcommand{\HOM}{\ensuremath{\textup{\textsc{Hom}}}} \DeclareMathOperator{\Isom}{Isom} \DeclareMathOperator{\Map}{Map} \DeclareMathOperator{\Mor}{Mor} \newcommand{\MOR}{\ensuremath{\textup{\textsc{Mor}}}} \DeclareMathOperator{\cofib}{cofib} \DeclareMathOperator{\coker}{coker} \DeclareMathOperator*{\colim}{colim} \DeclareMathOperator*{\hocolim}{hocolim} \DeclareMathOperator*{\holim}{holim} \DeclareMathOperator{\fib}{fib} \DeclareMathOperator{\Nerve}{N} \DeclareMathOperator{\trun}{\uptau} \DeclareMathOperator{\cosk}{ck} \DeclareMathOperator{\creff}{cr} \DeclareMathOperator{\ev}{ev} \DeclareMathOperator{\id}{id} \DeclareMathOperator{\pr}{pr} \DeclareMathOperator{\rk}{rk} \DeclareMathOperator{\sd}{sd} \DeclareMathOperator{\sk}{sk} \DeclareMathOperator{\specpos}{sp} \newcommand{\sdop}{\sd^{\op}} \newcommand{\paren}[1]{\left(#1\right)} \newcommand{\angs}[1]{\langle #1 \rangle} \newcommand{\quine}[1]{\ulcorner #1 \urcorner} \newcommand{\ultimes}{\,\underline{\times}\,} \newcommand{\horn}[2]{\upLambda_{#1}^{#2}} \newcommand{\categ}[1]{\textbf{\textup{#1}}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\intoo}[2]{\mathopen{]}#1\,;#2\mathclose{[}} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\ud}{\mathop{\mathrm{{}d}}\mathopen{}} \newcommand{\intff}[2]{\mathopen{[}#1\,;#2\mathclose{]}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section 8.1 Remainders and divisibility

The following theorem is the starting point for our studies on divisibility.

Theorem 8.1.1. The Remainder Theorem.

Let \(a\in\NN\) and \(b\in\ZZ\text{.}\) There are unique integers \(q\in \ZZ\) and \(0\leq r\lt a\) such that

\begin{equation*} b=qa+r\text{.} \end{equation*}

Proof.

We prove existence and uniqueness separately.

Existence: Let \(q\) be the largest integer for which \(qa\leq b\text{.}\) Let \(r=b-qa\geq 0\text{.}\) Then we must also have \(r\lt a\text{,}\) since if \(r\geq a\text{,}\) then \(b-qa\geq a\text{,}\) and so \(b-(q+1)a\geq 0\text{,}\) which contradicts \(q\) being the largest integer for which \(qa\leq b\text{.}\) This shows the existence of a pair \((q,r)\) satisfying the theorem.

Uniqueness: Assume that \((q',r')\) is a pair of integers such that \(b=q'a+r'\) and \(0\leq r'\lt a\text{.}\) Then

\begin{equation*} 0=b-b=q'a+r'-qa-r = (q'-q)a+(r'-r)\text{,} \end{equation*}

and so

\begin{equation*} r'-r=(q-q')a\text{.} \end{equation*}

Since \(0\leq r,r'\lt a\text{,}\) we know \(|r-r'|\lt a\text{.}\) Thus

\begin{equation*} a>|r-r'|=|(q-q')a|=|q-q'|\cdot a\text{,} \end{equation*}

which implies that \(1>|q-q'|\text{.}\) Since \(|q-q'|\) is a nonnegative integer, it therefore follows that \(q=q'\text{.}\)

Definition 8.1.2.

For two integers \(a\) and \(b\) we say \(a\) divides \(b\) if there is an integer \(c\) so that \(b=ac\text{.}\)

Some authors will write \(a | b\) for the sentence “\(a\) divides \(b\text{.}\)” (This isn't great notation.)

So for example, \(2\) divides \(4\text{,}\) but \(2\) does not divide \(3\text{.}\)

Lemma 8.1.3.

If \(a\) divides \(b\) and \(b\) divides \(a\text{,}\) then \(a=\pm b\text{.}\)

Proof.

Exercise.