----- > [!proposition] Proposition. ([[GCD is a linear combination]]) > Let $a,b \in \zz \cut \{ 0 \}$. There exist $r,s \in \zz$ [[greatest common divisor|such that]] $ra+sb=$ $\text{gcd}(a,b)$. ^c31ca8 > [!proof]- Proof. ([[GCD is a linear combination]]) Using the [[division algorithm]], write $a=bq+r$ for some $q,r \in \zz$ and recall that $\gcd(a,b)=\gcd(b,r)$ [^1]. If $r=0$, then $\gcd(b,r)=b=\gcd(a,b)=0a + 1b$ and we're done. Proceed recursively with $r=0$ as base case. Compute $\begin{align} a =& \textcolor{Thistle}{b}q_{1} + \textcolor{Skyblue}{r_{1}} \\ \textcolor{Thistle}{b} =& \textcolor{Skyblue}{r_{1}}q_{2} + \textcolor{LimeGreen}{r_{2}} \\ \textcolor{Skyblue}{r_{1}}= & \textcolor{LimeGreen}{r_{2}}q_{3} + \textcolor{Apricot}{r_{3}} \\ \textcolor{LimeGreen}{r_{2}}=& \textcolor{Apricot}{r_{3}}q_{4} + \textcolor{yellow}{r_{4}} \\ \vdots & \\ \textcolor{Apricot}{r_{n-1}}= & \textcolor{yellow}{r_{n}}q_{n+1} + \textcolor{magenta}{r_{n+1}} \\ \textcolor{yellow}{r_{n}}= & \textcolor{magenta}{r_{n+1}}q_{n+2} + \textcolor{olive}{\cancel{r_{n+2}}{^0} } \text{ (base case)} . \end{align}$ The **lemma** implies $\gcd(a,b)=\gcd(b,r_{1})=\gcd(r_{1},r_{2})=\dots=\gcd(r_{n+{1}}, \cancel{r_{n+2}}^{0})=r_{n+1},$ so we write $\begin{align} \gcd(a,b)=& \textcolor{magenta}{r_{n+1}} \\ = & \textcolor{Apricot}{r_{n-1}} - \textcolor{yellow}{r_{n}}q_{n+1} \\ = & \textcolor{Apricot}{r_{n-1}}-q_{n+1}(\textcolor{yellow}{r_{n-2}+r_{n-1}q_{n}}) \\ = & \textcolor{Apricot}{r_{n-1}} - q_{n+1}(\textcolor{yellow}{r_{n-2}}+\dots-q_{5}(\textcolor{LimeGreen}{r_{2}}-\textcolor{Apricot}{r_{3}}q_{4})) \\ = & \textcolor{Apricot}{r_{n-1}} - q_{n+1}(\textcolor{yellow}{r_{n-2}}+\dots-q_{5}(\textcolor{LimeGreen}{r_{2}}-q_{4}(\textcolor{Skyblue}{r_{1}}- q_{3}(\textcolor{Thistle}{b} - q_{2}(a - \textcolor{Thistle}{b}q_{1} ))))). \end{align}$ We may substitute in formulas for $r_{n-2}$, $r_{1}$, $r_{2}$, which are [[linear combination]]s of $a$ and $b$ and this will be the proof. ^494eb4 ----- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```