0
$\begingroup$

I am trying to solve the Diophantine equation using continuous fraction .

x ^ 2 - D * Y ^ 2 = 1

Keeping this document as reference

http://library.msri.org/books/Book44/files/01lenstra.pdf

In the page No. 3 , we have an example for Number 14.

If we write continuous fraction for 14 we get

[3; 1, 2, 1, 6]

Now , writing it as 3 + 1 / 1 + 1/ 2 + 1/ 1 + 1 / 6

once i derive i get , 15/ 4 which solves pells equation as

15 ^ 2 = 14 * 4 ^ 2 + 1

This is for even period and it works well.

Last line in the doc is given as

"If the period length is even, one proceeds as above; if the period length is odd, one truncates at the end of the second period [Buhler and Wagon 2008]."

But when i try for odd period , i dont get the correct answer ..

i took , 29 as the number

[5; 2, 1, 1, 2, 10]

when written as fraction , i get 727/135 which doesnt solve the equation

and i tried [5; 2, 1, 1, 2] , i got 70/29 which doesnt solve

and then tried [5; 2, 1, 1] i got 27/5. Even that doesnt solve

am i missing something ???

$\endgroup$
  • $\begingroup$ if there is a solution in integers to $x^2 - d y^2 = -1,$ which happens for $d=29, $ that solution will happen halfway. In this case, $70^2 - 29 \cdot 13^2 = -1,$ later $9801^2 - 29 \cdot 1820^2 = 1.$ $\endgroup$ – Will Jagy Aug 12 '15 at 1:40
  • $\begingroup$ But, how to arrive 9801/1820 using continuous fractions. Do we need to keep continuing the fractions ? $\endgroup$ – srinath Aug 12 '15 at 12:10
  • $\begingroup$ It says, "the end of the second period". So you carry out the continued fraction as far as $[5;2,1,1,2,10,2,1,1,2,10]$, and truncate by dropping the (last) $10$. $\endgroup$ – Gerry Myerson Aug 13 '15 at 23:17
1
$\begingroup$

This is how I like to write these out. The value of $x^2 - d y^2$ for $x=p$ and $y=q$ is written directly below each convergent $\frac{p}{q}.$ I recommend that you practice writing yours the same way, it helps to see that the values of $x^2 - d y^2$ also repeat in absolute value but have a $\pm$ switch when there does exist a solution to $x^2 - d y^2 = -1;$ so first we find $70^2 - 29 \cdot 13^2 = -1,$ only later do we find $9801^2 - 29 \cdot 1820^2 = 1.$

$$ \sqrt {29} $$

$$ \begin{array}{cccccccccccccccccccccccccccccc} & & 5 & & 2 & & 1 & & 1 & & 2 & & 10 & & 2 & & 1 & & 1 & & 2 & & 10 & \\ \frac{0}{1} & \frac{1}{0} & & \frac{5}{1} & & \frac{11}{2} & & \frac{16}{3} & & \frac{27}{5} & & \frac{70}{13} & & \frac{727}{135} & & \frac{1524}{283} & & \frac{2251}{418} & & \frac{3775}{701} & & \frac{9801}{1820} & & \frac{101785}{18901} \\ \\ -29 & 1 & & -4 & & 5 & & -5 & & 4 & & -1 & & 4 & & -5 & & 5 & & -4 & & 1 & & -4 \end{array} $$ We begin with two fake "convergents," first "$p/q = 0/1,$" and below that $0^2 - 29 \cdot 1^2 = -29.$ Next, "$p/q = 1/0,$" and below that $1^2 - 29 \cdot 0^2 = 1.$

Then our first genuine convergent, $p/q = 5/1,$ and below that $5^2 - 29 \cdot 1^2 = -4.$ Next, $p/q = 11/2,$ and below that $11^2 - 29 \cdot 2^2 = 5.$

A few steps later, $p/q = 70/13,$ and below that $70^2 - 29 \cdot 13^2 = -1.$

Several more steps later, $p/q = 9801/1820,$ and below that $9801^2 - 29 \cdot 1820^2 = 1.$

Smaller displays so that the entire calculation might fit in the intended width:

First we use the command "small:"

$$ \small \begin{array}{cccccccccccccccccccccccccccccc} & & 5 & & 2 & & 1 & & 1 & & 2 & & 10 & & 2 & & 1 & & 1 & & 2 & & 10 & \\ \frac{0}{1} & \frac{1}{0} & & \frac{5}{1} & & \frac{11}{2} & & \frac{16}{3} & & \frac{27}{5} & & \frac{70}{13} & & \frac{727}{135} & & \frac{1524}{283} & & \frac{2251}{418} & & \frac{3775}{701} & & \frac{9801}{1820} & & \frac{101785}{18901} \\ \\ -29 & 1 & & -4 & & 5 & & -5 & & 4 & & -1 & & 4 & & -5 & & 5 & & -4 & & 1 & & -4 \end{array} $$

now scriptsize

$$ \scriptsize \begin{array}{cccccccccccccccccccccccccccccc} & & 5 & & 2 & & 1 & & 1 & & 2 & & 10 & & 2 & & 1 & & 1 & & 2 & & 10 & \\ \frac{0}{1} & \frac{1}{0} & & \frac{5}{1} & & \frac{11}{2} & & \frac{16}{3} & & \frac{27}{5} & & \frac{70}{13} & & \frac{727}{135} & & \frac{1524}{283} & & \frac{2251}{418} & & \frac{3775}{701} & & \frac{9801}{1820} & & \frac{101785}{18901} \\ \\ -29 & 1 & & -4 & & 5 & & -5 & & 4 & & -1 & & 4 & & -5 & & 5 & & -4 & & 1 & & -4 \end{array} $$

Next we use "tiny"

$$ \tiny \begin{array}{cccccccccccccccccccccccccccccc} & & 5 & & 2 & & 1 & & 1 & & 2 & & 10 & & 2 & & 1 & & 1 & & 2 & & 10 & \\ \frac{0}{1} & \frac{1}{0} & & \frac{5}{1} & & \frac{11}{2} & & \frac{16}{3} & & \frac{27}{5} & & \frac{70}{13} & & \frac{727}{135} & & \frac{1524}{283} & & \frac{2251}{418} & & \frac{3775}{701} & & \frac{9801}{1820} & & \frac{101785}{18901} \\ \\ -29 & 1 & & -4 & & 5 & & -5 & & 4 & & -1 & & 4 & & -5 & & 5 & & -4 & & 1 & & -4 \end{array} $$

That is pretty good, please concentrate on the line of $x^2 - d y^2$ values, maybe ignore the initial $-29,$ so $$ 1, \; -4, \; 5, \; -5, \; 4, \; -1, \; 4, \; -5, \; 5, \; -4, \; 1, \; -4, \ldots $$

I got instructions on re-sizing Latex at What are some options for putting another, smaller copy of this long Latex item?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.