Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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,,rn0, 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)=Q1iQ12(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)=(011qi)(xi1yi1xiyi)with(x1y1x2y2)=(1001)

Proof

The initial follows, because

r1=r11+r20

r2=r10+r21

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)=Q1i(ri1ri)(xiyixi+1yi+1)=Q1i(xi1yi1xiyi)

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+xi1

yi+1=qiyi+yi1


This page titled 3.5: Recursive Solution of x and y in the Diophantine Equation is shared under a CC BY-NC license and was authored, remixed, and/or curated by J. J. P. Veerman (PDXOpen: Open Educational Resources) .

Support Center

How can we help?