A calculus of the absurd
\(\newcommand{\footnotename}{footnote}\)
\(\def \LWRfootnote {1}\)
\(\newcommand {\footnote }[2][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\newcommand {\footnotemark }[1][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\let \LWRorighspace \hspace \)
\(\renewcommand {\hspace }{\ifstar \LWRorighspace \LWRorighspace }\)
\(\newcommand {\mathnormal }[1]{{#1}}\)
\(\newcommand \ensuremath [1]{#1}\)
\(\newcommand {\LWRframebox }[2][]{\fbox {#2}} \newcommand {\framebox }[1][]{\LWRframebox } \)
\(\newcommand {\setlength }[2]{}\)
\(\newcommand {\addtolength }[2]{}\)
\(\newcommand {\setcounter }[2]{}\)
\(\newcommand {\addtocounter }[2]{}\)
\(\newcommand {\arabic }[1]{}\)
\(\newcommand {\number }[1]{}\)
\(\newcommand {\noalign }[1]{\text {#1}\notag \\}\)
\(\newcommand {\cline }[1]{}\)
\(\newcommand {\directlua }[1]{\text {(directlua)}}\)
\(\newcommand {\luatexdirectlua }[1]{\text {(directlua)}}\)
\(\newcommand {\protect }{}\)
\(\def \LWRabsorbnumber #1 {}\)
\(\def \LWRabsorbquotenumber "#1 {}\)
\(\newcommand {\LWRabsorboption }[1][]{}\)
\(\newcommand {\LWRabsorbtwooptions }[1][]{\LWRabsorboption }\)
\(\def \mathchar {\ifnextchar "\LWRabsorbquotenumber \LWRabsorbnumber }\)
\(\def \mathcode #1={\mathchar }\)
\(\let \delcode \mathcode \)
\(\let \delimiter \mathchar \)
\(\def \oe {\unicode {x0153}}\)
\(\def \OE {\unicode {x0152}}\)
\(\def \ae {\unicode {x00E6}}\)
\(\def \AE {\unicode {x00C6}}\)
\(\def \aa {\unicode {x00E5}}\)
\(\def \AA {\unicode {x00C5}}\)
\(\def \o {\unicode {x00F8}}\)
\(\def \O {\unicode {x00D8}}\)
\(\def \l {\unicode {x0142}}\)
\(\def \L {\unicode {x0141}}\)
\(\def \ss {\unicode {x00DF}}\)
\(\def \SS {\unicode {x1E9E}}\)
\(\def \dag {\unicode {x2020}}\)
\(\def \ddag {\unicode {x2021}}\)
\(\def \P {\unicode {x00B6}}\)
\(\def \copyright {\unicode {x00A9}}\)
\(\def \pounds {\unicode {x00A3}}\)
\(\let \LWRref \ref \)
\(\renewcommand {\ref }{\ifstar \LWRref \LWRref }\)
\( \newcommand {\multicolumn }[3]{#3}\)
\(\require {textcomp}\)
\(\newcommand {\LWRmarginnote }[1][]{}\)
\(\newcommand {\marginnote }[2][]{\qquad {\small \textrm {#2}}\LWRmarginnote }\)
\(\def \LWRsidenote {1}\)
\(\newcommand {\sidenotemark }[1][\LWRsidenote ]{{}^{\mathrm {#1}}}\)
\(\newcommand {\intertext }[1]{\text {#1}\notag \\}\)
\(\let \Hat \hat \)
\(\let \Check \check \)
\(\let \Tilde \tilde \)
\(\let \Acute \acute \)
\(\let \Grave \grave \)
\(\let \Dot \dot \)
\(\let \Ddot \ddot \)
\(\let \Breve \breve \)
\(\let \Bar \bar \)
\(\let \Vec \vec \)
\(\newcommand {\nicefrac }[3][]{\mathinner {{}^{#2}\!/\!_{#3}}}\)
\(\newcommand {\unit }[2][]{#1 \mathinner {#2}}\)
\(\newcommand {\unitfrac }[3][]{#1 \mathinner {{}^{#2}\!/\!_{#3}}}\)
\(\newcommand {\bm }[1]{\boldsymbol {#1}}\)
\(\require {mathtools}\)
\(\newenvironment {crampedsubarray}[1]{}{}\)
\(\newcommand {\smashoperator }[2][]{#2\limits }\)
\(\newcommand {\SwapAboveDisplaySkip }{}\)
\(\newcommand {\LaTeXunderbrace }[1]{\underbrace {#1}}\)
\(\newcommand {\LaTeXoverbrace }[1]{\overbrace {#1}}\)
\(\newcommand {\LWRmultlined }[1][]{\begin {multline*}}\)
\(\newenvironment {multlined}[1][]{\LWRmultlined }{\end {multline*}}\)
\(\let \LWRorigshoveleft \shoveleft \)
\(\renewcommand {\shoveleft }[1][]{\LWRorigshoveleft }\)
\(\let \LWRorigshoveright \shoveright \)
\(\renewcommand {\shoveright }[1][]{\LWRorigshoveright }\)
\(\newcommand {\shortintertext }[1]{\text {#1}\notag \\}\)
\(\newcommand {\vcentcolon }{\mathrel {\unicode {x2236}}}\)
\(\newcommand {\Var }{\operatorname {Var}}\)
\(\newcommand {\Expected }{\operatorname {E}}\)
\(\newcommand {\abs }[1]{\left \lvert #1\right \rvert }\)
\(\newcommand {\norm }[1]{\left \lVert #1\right \rVert }\)
\(\newcommand {\rbrackets }[1]{\left (#1\right )}\)
\(\newcommand {\sbrackets }[1]{\left [#1\right ]}\)
\(\newcommand {\cbrackets }[1]{\left \{#1\right \}}\)
\(\newcommand {\RE }{\operatorname {Re}}\)
\(\newcommand {\IM }{\operatorname {IM}}\)
\(\newcommand {\Span }{\operatorname {span}}\)
19.1.3 Bezout’s lemma
-
Theorem 19.1.2 Let \(a, b \in \mathbb {Z}\), then there exists some integers \(x\) and \(y\) such that \(\gcd (a, b) = xa + yb\).
TODO: proof
-
Example 19.1.1 Prove that for all \(a, b, c \in \mathbb {N} - \{0\}\) it is true that
\(\seteqnumber{0}{19.}{17}\)\begin{equation} \gcd (a, bc) | \gcd (a, b) \times \gcd (a, c) \end{equation}
We know using Bezout’s lemma that there exist some \(w, z, y, z \in \mathbb {Z}\) such that \(\gcd (a, b) = wa + xb\) and \(\gcd (a, c) = ya + zc\), and therefore
\(\seteqnumber{0}{19.}{18}\)\begin{align} \gcd (a, b) \times \gcd (a, c) &= (wa + xb)(ya + zc) \\ &= waya + wazc + xbya + xbzc \\ &= (way + wzc + xby)a + (xz)bc \end{align}
and therefore as \(\gcd (a, bc)\) divides both \(a\) and \(bc\) it divides the expression we are after.
\(\Box \)