3.5: Solución Recursiva de x e Y en la Ecuación Diofantina

Última actualización
Guardar como PDF

Page ID: 111485

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

El teorema 3.4 tiene dos corolarios interesantes. El primero de hecho se afirma en la prueba de ese teorema, y el segundo requiere una prueba muy breve. Haremos un uso extensivo de estos dos resultados en el Capítulo 6 cuando discutamos fracciones continuas.

Corolario 3.11

Dado\(r_{1}, r_{2}\), y sus sucesivos restos\(r_{3}, \cdots, r_{n} \ne 0\), y\(r_{n+1} = 0\) en el algoritmo euclidiano. Entonces para\(i \in \{3, \cdots, n\}\), la solución for\((x_{i}, y_{i})\) in\(r_{i} = r_{1}x_{i} +r_{2}y_{i}\) viene dada por:

\[\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\]

Corolario 3.12

Dado\(r_{1}, r_{2}\), y sus cocientes sucesivos\(q_{2}\) a través de\(q_{n}\) como en la ecuación 3.1, entonces\(x_{i}\) y\(y_{i}\) del Corolario 3.11 pueden resolverse de la siguiente manera:

\[\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\]

Prueba

La inicial sigue, porque

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

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

Observe que, por definición,

\[\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\]

Del Corolario 3.11, ahora tenemos que

\[\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\]

De esto, se deducen las ecuaciones para\(x_{i+1}\) y\(y_{i+1}\).

Observamos que la recursión en el Corolario 3.12 también puede expresarse como

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

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