3.5: Recursive Solution of x and y in the Diophantine Equation

Last updated
Save as PDF

Page ID: 60312

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

Theorem 3.4 has two interesting corollaries. The first is in fact stated in the proof of that theorem, and the second requires a very short proof. We will make extensive use of these two results in Chapter 6 when we discuss continued fractions.

Corollary 3.11

Given \(r_{1}, r_{2}\), and their successive remainders \(r_{3}, \cdots, r_{n} \ne 0\), and \(r_{n+1} = 0\) in the Euclidean algorithm. Then for \(i \in \{3, \cdots, n\}\), the solution for \((x_{i}, y_{i})\) in \(r_{i} = r_{1}x_{i} +r_{2}y_{i}\) is given by:

\[\begin{pmatrix} {r_{i}}\\ {r_{i+1}} \end{pmatrix} = Q_{i}^{-1} \cdots Q_{2}^{-1} \begin{pmatrix} {r_1}\\ {r_{2}} \end{pmatrix} \nonumber\]

Corollary 3.12

Given \(r_{1}, r_{2}\), and their successive quotients \(q_{2}\) through \(q_{n}\) as in equation 3.1, then \(x_{i}\) and \(y_{i}\) of Corollary 3.11 can be solved as follows:

\[\begin{array} {ccc} {\begin{pmatrix} {x_{i}}&{y_{i}}\\ {x_{i+1}}&{y_{i+1}} \end{pmatrix} = \begin{pmatrix} {0}&{1}\\ {1}&{-q_{i}} \end{pmatrix} \begin{pmatrix} {x_{i-1}}&{y_{i-1}}\\ {x_{i}}&{y_{i}} \end{pmatrix}}&{with}&{\begin{pmatrix} {x_{1}}&{y_{1}}\\ {x_{2}}&{y_{2}} \end{pmatrix} = \begin{pmatrix} {1}&{0}\\ {0}&{1} \end{pmatrix}} \end{array} \nonumber\]

Proof

The initial follows, because

\[r_{1} = r_{1} \cdot 1+r_{2} \cdot 0 \nonumber\]

\[r_{2} = r_{1} \cdot 0+r_{2} \cdot 1 \nonumber\]

Notice that, by definition,

\[\begin{pmatrix} {r_{i}}\\ {r_{i+1}} \end{pmatrix} = \begin{pmatrix} {r_{1}x_{i}+r_{2}y_{i}}\\ {r_{1}x_{i+1}+r_{2}y_{i+1}} \end{pmatrix} = \begin{pmatrix} {x_{i}}&{y_{i}}\\ {x_{i+1}}&{y_{i+1}} \end{pmatrix} \begin{pmatrix} {r_1}\\ {r_{2}} \end{pmatrix} \nonumber\]

From Corollary 3.11, we now have that

\[\begin{pmatrix} {r_{i}}\\ {r_{i+1}} \end{pmatrix} = Q_{i}^{-1} \begin{pmatrix} {r_{i-1}}\\ {r_{i}} \end{pmatrix} \Rightarrow \begin{pmatrix} {x_{i}}&{y_{i}}\\ {x_{i+1}}&{y_{i+1}} \end{pmatrix} = Q_{i}^{-1} \begin{pmatrix} {x_{i-1}}&{y_{i-1}}\\ {x_{i}}&{y_{i}} \end{pmatrix} \nonumber\]

From this, one deduces the equations for \(x_{i+1}\) and \(y_{i+1}\).

We remark that the recursion in Corollary 3.12 can also be expressed as

\[x_{i+1} = -q_{i}x_{i}+x_{i-1} \nonumber\]

\[y_{i+1} = -q_{i}y_{i}+y_{i-1} \nonumber\]