Multiplicative theory of integers

Skip to main content

\( \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}{&} \)

Chapter 8 Multiplicative theory of integers

This week we will study the integers, particularly the techniques of studying divisibility, the highest common factor, and prime factorization.

These techniques are especially useful for solving diophantine equations, which are polynomial equations where we seek integer solutions. The most famous diophantine equation is

\begin{equation*} x^{n}+y^{n}=z^{n} \end{equation*}

It was famously claimed by Fermat (without proof) that there are solutions \(x,y,z,n\in\NN\) only if \(n=1\) or \(n=2\text{.}\) It wasn't until 1994 when Andrew Wiles actually gave a proof.

This week's set of tools are also useful when we are trying to show at a diophantine can't be solved. You have seen one such proof before: that \(\sqrt{2}\) is irrational. Let's recall the proof briefly:

Suppose there was a rational number \(\frac{m}{n}\) (where \(m\) and \(n\) are reduced in the sense that they have no common divisors apart from \(1\)) so that \(\left(\frac{m}{n}\right)^2=2\text{,}\) then \(m^2=2n^2\text{.}\) This means that \(m^2\) is even. Then \(m\) must be even since, if instead \(m=2k+1\) for some integer \(k\text{,}\) then \(m^2=(2k+1)^2=4(k^2+k)+1\text{,}\) which is odd, a contradiction. Hence, \(m=2k\) for some integer \(k\text{,}\) and so

\begin{equation*} 2n^2=m^2=(2k)^2=4k^2 \end{equation*}

and so \(n^2=2k^2\text{,}\) and using a similar reasoning, we get that \(n\) must also be even, which is a contradiction since we assumed \(m\) and \(n\) had no common factors, but now we have shown they are both divisible by \(2\text{.}\)

The important feature of the proof was to use the coprimality of \(m\) and \(n\text{,}\) that is, that they share no common divisors, as well as the fact that if \(m^2\) is divisible by \(2\) (that is, if \(m^2\) was even, then so was \(m\)). If we want to generalize this proof, we will need to develop these tools about divisibility and coprimality. Later, we will in fact show that \(\sqrt{n}\) is rational exactly when \(n=m^2\) for some integer \(m\text{.}\)

As motivation for the techniques we develop along the way, we will show how they can be used to solve various diophantine equations. As a special final application of these techniques, we'll also classify all Pythagorean Triples, that is, integers \(x,y,z\) so that

\begin{equation*} x^2+y^2=z^2\text{.} \end{equation*}