Proof Using Pell's EquationDate: 09/18/1999 at 04:49:02 From: Tran Nam Dung Subject: Continued fractions Solving the Pell equation x^2 - Dy^2 = 1 for different D, finding the minimal solution (x0,y0) by using continued fractions, I determined that if 1 Sqrt(D)= a1 + ----------------------- 1 a2 + ------------------ a3 + ... k an + --------- sqrt(D)+t and p/q = [a1;a2;...;an] then p^2 - D.q^2 = (-1)^n.k I tried to prove this fact, but couldn't. Please help me with instructions or some hints. Thanks a lot. Namdung (Viet Nam) Date: 09/18/1999 at 11:01:19 From: Doctor Anthony Subject: Re: Continued fractions I'll be using the notation x^2 - d.y^2 = 1 for Pell's equation. We must show that if p/q is a convergent of the continued fraction expansion of sqrt(d) then x = p, y = q is a solution of one of the equations x^2 - d.y^2 = k where |k| < 1 + 2.sqrt(d) If p/q is a convergent of sqrt(d) then we have: |sqrt(d) - p/q| < 1/q^2 (a property of convergents) and multiplying through by q: |p - q.sqrt(d)| < 1/q .................................(1) but |p + q.sqrt(q)| = |(p - q.sqrt(q)) + 2q.sqrt(d)| <= |p - q.sqrt(d)| + |2q.sqrt(d)| < 1/q + 2q.sqrt(d) < (1 + 2.sqrt(d))q So |p + q.sqrt(d)| < (1 + 2.sqrt(d)).q ...................(2) Combining the inequalities (1) and (2) we get: |p^2 - d.q^2| = |p - q.sqrt(d)|.|p + q.sqrt(d)| < (1/q)(1 + 2.sqrt(d)).q = 1 + 2.sqrt(d) In general not all the convergents p(n)/q(n) of sqrt(d) give solutions to x^2 - d.y^2 = 1, but the above reasoning gives us information about the size of the values taken on by the sequence p^2 - d.q^2. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/