3.2: A Particular Solution of ax+by = c
- Page ID
- 60309
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Another interesting way to encode the computations done in equations 3.1 and 3.2 is via matrices.
\[\begin{pmatrix} {r_{i-1}}\\ {r_{i}} \end{pmatrix} = \begin{pmatrix} {q_{1}}&{1}\\ {1}&{0} \end{pmatrix} \begin{pmatrix} {r_{i}}\\ {r_{i+1}} \end{pmatrix}\]
Denote the matrix in this equation by \(Q_{i}\). Its determinant equals \(-1\), and so it is invertible. In fact,
\[\begin{array} {ccc} {Q_{i} = \begin{pmatrix} {q_{i}}&{1}\\ {1}&{0} \end{pmatrix}}&{and}&{Q_{i}^{-1} = \begin{pmatrix} {0}&{1}\\ {1}&{-q_{i}} \end{pmatrix}} \end{array}\]
These matrices \(Q_{i}\) are very interesting. We will use them again to study the theory of continued fractions in Chapter 6. For now , as we will see in Theorem 3.4, they give us an explicit algorithm to find a solution to the equation \(r_{1}x+r_{2}y = r \gcd(r_{1}, r_{2})\). Note that from Bezout's Lemma (Lemma 2.5), we already know this has a solution. But the next result gives us a simple way to actually calculate a solution. In what follows \(X_{ij}\) means the \((i,j)\) entry of the matrix \(X\).
Theorem 3.4
Give \(r_{1}\) and \(r_{2}\), a solution for \(x\) and \(y\) of \(r_{1}x+r_{2}y = r \gcd(r_{1},r_{2})\) is given by
\[\begin{array}{ccc} {x = r(Q_{n-1}^{-1} \cdots Q_{2}^{-1})_{2,1}}&{and}&{x = r(Q_{n-1}^{-1} \cdots Q_{2}^{-1})_{2,2}} \nonumber \end{array}\]
- Proof
-
Let \(r_{i},q_{i}\), and \(Q_{i}\) be defined as above, and set \(r_{n+1} = 0\). From equation 3.4, we have
\[\begin{pmatrix} {r_{i}}\\ {r_{i+1}} \end{pmatrix} = Q_{i}^{-1} \begin{pmatrix} {r_{i-1}}\\ {r_{i}} \end{pmatrix} \Rightarrow r \begin{pmatrix} {r_{n-1}}\\ {r_{n}} \end{pmatrix} = r Q_{n-1}^{-1} \cdots Q_{2}^{-1} \begin{pmatrix} {r_{1}}\\ {r_{2}} \end{pmatrix} \nonumber\]
Observe that \(r_{n+1} = 0\) and so \(\gcd (r_{1},r_{2} = r_{n}\) and
\[\begin{pmatrix} {r_{n-1}}\\ {r_{n}} \end{pmatrix} = \begin{pmatrix} {x_{n-1}}&{y_{n-1}}\\ {x_{n}}&{y_{n}} \end{pmatrix} \begin{pmatrix} {r_{1}}\\ {r_{2}} \end{pmatrix}\]
The equalities follow immediately.
In practice, rather than multiplying all these matrices, it may be more convenient to solve equation 3.1 or 3.2 “backward”, as the expression goes. This can be done as follows. Start with
\[\gcd(r_{1}, r_{2}) = r_{n} = r_{n-2}-r_{n-1}q_{n-1} \nonumber\]
which follows from equation 3.1. The line above it in that same equation gives \(r_{n-1} = r_{n-3}-r_{n-2}q_{n-2}\). Use this to eliminate \(r_{n-1}\) in favor of \(r_{n-2}\) and \(r_{n-3}\). So,
\[\gcd(r_{1}, r_{2}) = r_{n} = r_{n-2}-(r_{n-3}-r_{n-2} q_{n-2}) q_{n-1} \nonumber\]
\[= r_{n-2} (1+q_{n-1}q_{n-2})+r_{n-3}(-q_{n-1}) \nonumber\]
This computation can be done still more efficiently by employing the notation of equation 3.2 again.
(The signs added in the first line in this scheme serve only to keep track of the signs of the coefficients in lines three and below.) Applying this to the example gives
Adding the last two lines gives that \(2 = 158(25) + 188(-21)\).