3.5: Recursive Solution of x and y in the Diophantine Equation
( \newcommand{\kernel}{\mathrm{null}\,}\)
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 r1,r2, and their successive remainders r3,⋯,rn≠0, and rn+1=0 in the Euclidean algorithm. Then for i∈{3,⋯,n}, the solution for (xi,yi) in ri=r1xi+r2yi is given by:
(riri+1)=Q−1i⋯Q−12(r1r2)
Corollary 3.12
Given r1,r2, and their successive quotients q2 through qn as in equation 3.1, then xi and yi of Corollary 3.11 can be solved as follows:
(xiyixi+1yi+1)=(011−qi)(xi−1yi−1xiyi)with(x1y1x2y2)=(1001)
- Proof
-
The initial follows, because
r1=r1⋅1+r2⋅0
r2=r1⋅0+r2⋅1
Notice that, by definition,
(riri+1)=(r1xi+r2yir1xi+1+r2yi+1)=(xiyixi+1yi+1)(r1r2)
From Corollary 3.11, we now have that
(riri+1)=Q−1i(ri−1ri)⇒(xiyixi+1yi+1)=Q−1i(xi−1yi−1xiyi)
From this, one deduces the equations for xi+1 and yi+1.
We remark that the recursion in Corollary 3.12 can also be expressed as
xi+1=−qixi+xi−1
yi+1=−qiyi+yi−1