How to find a fundamental solution to Pell's equation?

It is quite straightforward to find the fundamental solutions for a given Pell's equation when $d$ is small. But I am unable to solve this equation, as I'm unable to find the fundamental solutions:

Solve: $x^2-29y^2=1$ and $x^2-29y^2=-1$ with $y\not=0$.

Could you please guide me through the solution

(Too long for a comment.)

If you're lucky and your discriminant $d$ has a certain form ($d = 5, 13, 21, 29, 53, 61, \dots$), you can use the smaller fundamental solutions of the Pell equation,

$$p^2-dq^2 = -4\tag{1}$$

Let,

$$\left(\frac{p+q\sqrt{d}}{2}\right)^3=u+v\sqrt{d}\tag2$$

$$\left(\frac{p+q\sqrt{d}}{2}\right)^6=x+y\sqrt{d}\tag3$$

then,

$$u^2-dv^2 = -1\tag4$$

$$x^2-dy^2 = 1\tag5$$

If fundamental $p,q$ are odd, then $(2),(3)$ are also fundamental. For your $d=29$, it is just $p,q = 5,1$. Hence the fundamental unit,

$$U_{29} =\tfrac{5+\sqrt{29}}{2}$$

and,

$$\big(U_{29}\big)^3=70+13\sqrt{29},\quad \text{thus}\;\;\color{blue}{70}^2-29\cdot\color{blue}{13}^2=-1$$

$$\big(U_{29}\big)^6=9801+1820\sqrt{29},\quad \text{thus}\;\;\color{blue}{9801}^2-29\cdot1820^2=1$$

$$2^6\left(\big(U_{29}\big)^6+\big(U_{29}\big)^{-6}\right)^2 =\color{blue}{396^4}$$

Incidentally, since certain eta quotients involve $U_{29}$, we find those integers all over Ramanujan's famous pi formula,

$$\frac{1}{\pi} = \frac{2 \sqrt 2}{\color{blue}{9801}} \sum_{k=0}^\infty \frac{(4k)!}{k!^4} \frac{29\cdot\color{blue}{70\cdot13}\,k+1103}{\color{blue}{(396^4)}^k}$$

Nice, eh?

The standard method for finding the fundamental solution is continued fractions for $\sqrt {29},$ and would not be difficult with a calculator. HERE is a summary using $\sqrt 7$ instead. Gauss and Lagrange made an equivalent but better method with "reduced" quadratic forms, that requires no decimal accuracy for the square root, just the integer part, just integer arithmetic, and no "cycle detection." I have described it often on this site.

http://zakuski.utsa.edu/~jagy/BLOG_2014_July_15.pdf

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell 29


0  form   1 10 -4   delta  -2
1  form   -4 6 5   delta  1
2  form   5 4 -5   delta  -1
3  form   -5 6 4   delta  2
4  form   4 10 -1   delta  -10
5  form   -1 10 4   delta  2
6  form   4 6 -5   delta  -1
7  form   -5 4 5   delta  1
8  form   5 6 -4   delta  -2
9  form   -4 10 1   delta  10
10  form   1 10 -4



 Pell automorph 
9801  52780
1820  9801

Pell unit 
9801^2 - 29 * 1820^2 = 1 

=========================================

Pell NEGATIVE 
70^2 - 29 * 13^2 = -1 

=========================================

  4 PRIMITIVE 
27^2 - 29 * 5^2 = 4 

=========================================

  -4 PRIMITIVE 
3775^2 - 29 * 701^2 = -4


NOTE by hand:  5^2 - 29 * 1^2 = -4 
was passed over by my program; that's life. 

=========================================

Well. The general, reliable method is continued fractions. Doing these with an ordinary calculator for $\sqrt n$ will work nicely for most small $n.$ However, as you can check in various places, this becomes problematic for $\sqrt {61}.$ You can switch to continued fractions with large decimal accuracy on computer, but eventually one runs into problems. The method above is very similar to continued fractions, it just has a more careful style of bookkeeping, with the result that it always works. The fundamental theorem here is due to Lagrange, I will put a jpeg from a 1929 book by L. E. Dickson, it is Theorem 85. Notice that everyone is now using LED light bulbs, that can't be a coincidence.

Method described by Prof. Lubin at Continued fraction of $\sqrt{67} - 4$

$$ \sqrt { 29} = 5 + \frac{ \sqrt {29} - 5 }{ 1 } $$ $$ \frac{ 1 }{ \sqrt {29} - 5 } = \frac{ \sqrt {29} + 5 }{4 } = 2 + \frac{ \sqrt {29} - 3 }{4 } $$ $$ \frac{ 4 }{ \sqrt {29} - 3 } = \frac{ \sqrt {29} + 3 }{5 } = 1 + \frac{ \sqrt {29} - 2 }{5 } $$ $$ \frac{ 5 }{ \sqrt {29} - 2 } = \frac{ \sqrt {29} + 2 }{5 } = 1 + \frac{ \sqrt {29} - 3 }{5 } $$ $$ \frac{ 5 }{ \sqrt {29} - 3 } = \frac{ \sqrt {29} + 3 }{4 } = 2 + \frac{ \sqrt {29} - 5 }{4 } $$ $$ \frac{ 4 }{ \sqrt {29} - 5 } = \frac{ \sqrt {29} + 5 }{1 } = 10 + \frac{ \sqrt {29} - 5 }{1 } $$

Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccccccccccccc} & & 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 } \\ \\ & 1 & & -4 & & 5 & & -5 & & 4 & & -1 & & 4 & & -5 & & 5 & & -4 & & 1 \end{array} $$

$$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 29 \cdot 0^2 = 1 & \mbox{digit} & 5 \\ \frac{ 5 }{ 1 } & 5^2 - 29 \cdot 1^2 = -4 & \mbox{digit} & 2 \\ \frac{ 11 }{ 2 } & 11^2 - 29 \cdot 2^2 = 5 & \mbox{digit} & 1 \\ \frac{ 16 }{ 3 } & 16^2 - 29 \cdot 3^2 = -5 & \mbox{digit} & 1 \\ \frac{ 27 }{ 5 } & 27^2 - 29 \cdot 5^2 = 4 & \mbox{digit} & 2 \\ \frac{ 70 }{ 13 } & 70^2 - 29 \cdot 13^2 = -1 & \mbox{digit} & 10 \\ \frac{ 727 }{ 135 } & 727^2 - 29 \cdot 135^2 = 4 & \mbox{digit} & 2 \\ \frac{ 1524 }{ 283 } & 1524^2 - 29 \cdot 283^2 = -5 & \mbox{digit} & 1 \\ \frac{ 2251 }{ 418 } & 2251^2 - 29 \cdot 418^2 = 5 & \mbox{digit} & 1 \\ \frac{ 3775 }{ 701 } & 3775^2 - 29 \cdot 701^2 = -4 & \mbox{digit} & 2 \\ \frac{ 9801 }{ 1820 } & 9801^2 - 29 \cdot 1820^2 = 1 & \mbox{digit} & 10 \\ \end{array} $$

======================================================================================

$$ \sqrt { 95} = 9 + \frac{ \sqrt {95} - 9 }{ 1 } $$ $$ \frac{ 1 }{ \sqrt {95} - 9 } = \frac{ \sqrt {95} + 9 }{14 } = 1 + \frac{ \sqrt {95} - 5 }{14 } $$ $$ \frac{ 14 }{ \sqrt {95} - 5 } = \frac{ \sqrt {95} + 5 }{5 } = 2 + \frac{ \sqrt {95} - 5 }{5 } $$ $$ \frac{ 5 }{ \sqrt {95} - 5 } = \frac{ \sqrt {95} + 5 }{14 } = 1 + \frac{ \sqrt {95} - 9 }{14 } $$ $$ \frac{ 14 }{ \sqrt {95} - 9 } = \frac{ \sqrt {95} + 9 }{1 } = 18 + \frac{ \sqrt {95} - 9 }{1 } $$

Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccc} & & 9 & & 1 & & 2 & & 1 & & 18 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 9 }{ 1 } & & \frac{ 10 }{ 1 } & & \frac{ 29 }{ 3 } & & \frac{ 39 }{ 4 } \\ \\ & 1 & & -14 & & 5 & & -14 & & 1 \end{array} $$

$$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 95 \cdot 0^2 = 1 & \mbox{digit} & 9 \\ \frac{ 9 }{ 1 } & 9^2 - 95 \cdot 1^2 = -14 & \mbox{digit} & 1 \\ \frac{ 10 }{ 1 } & 10^2 - 95 \cdot 1^2 = 5 & \mbox{digit} & 2 \\ \frac{ 29 }{ 3 } & 29^2 - 95 \cdot 3^2 = -14 & \mbox{digit} & 1 \\ \frac{ 39 }{ 4 } & 39^2 - 95 \cdot 4^2 = 1 & \mbox{digit} & 18 \\ \end{array} $$

=================================================================================

$$ \sqrt { 74} = 8 + \frac{ \sqrt {74} - 8 }{ 1 } $$ $$ \frac{ 1 }{ \sqrt {74} - 8 } = \frac{ \sqrt {74} + 8 }{10 } = 1 + \frac{ \sqrt {74} - 2 }{10 } $$ $$ \frac{ 10 }{ \sqrt {74} - 2 } = \frac{ \sqrt {74} + 2 }{7 } = 1 + \frac{ \sqrt {74} - 5 }{7 } $$ $$ \frac{ 7 }{ \sqrt {74} - 5 } = \frac{ \sqrt {74} + 5 }{7 } = 1 + \frac{ \sqrt {74} - 2 }{7 } $$ $$ \frac{ 7 }{ \sqrt {74} - 2 } = \frac{ \sqrt {74} + 2 }{10 } = 1 + \frac{ \sqrt {74} - 8 }{10 } $$ $$ \frac{ 10 }{ \sqrt {74} - 8 } = \frac{ \sqrt {74} + 8 }{1 } = 16 + \frac{ \sqrt {74} - 8 }{1 } $$

Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccccccccccccc} & & 8 & & 1 & & 1 & & 1 & & 1 & & 16 & & 1 & & 1 & & 1 & & 1 & & 16 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 8 }{ 1 } & & \frac{ 9 }{ 1 } & & \frac{ 17 }{ 2 } & & \frac{ 26 }{ 3 } & & \frac{ 43 }{ 5 } & & \frac{ 714 }{ 83 } & & \frac{ 757 }{ 88 } & & \frac{ 1471 }{ 171 } & & \frac{ 2228 }{ 259 } & & \frac{ 3699 }{ 430 } \\ \\ & 1 & & -10 & & 7 & & -7 & & 10 & & -1 & & 10 & & -7 & & 7 & & -10 & & 1 \end{array} $$

$$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 74 \cdot 0^2 = 1 & \mbox{digit} & 8 \\ \frac{ 8 }{ 1 } & 8^2 - 74 \cdot 1^2 = -10 & \mbox{digit} & 1 \\ \frac{ 9 }{ 1 } & 9^2 - 74 \cdot 1^2 = 7 & \mbox{digit} & 1 \\ \frac{ 17 }{ 2 } & 17^2 - 74 \cdot 2^2 = -7 & \mbox{digit} & 1 \\ \frac{ 26 }{ 3 } & 26^2 - 74 \cdot 3^2 = 10 & \mbox{digit} & 1 \\ \frac{ 43 }{ 5 } & 43^2 - 74 \cdot 5^2 = -1 & \mbox{digit} & 16 \\ \frac{ 714 }{ 83 } & 714^2 - 74 \cdot 83^2 = 10 & \mbox{digit} & 1 \\ \frac{ 757 }{ 88 } & 757^2 - 74 \cdot 88^2 = -7 & \mbox{digit} & 1 \\ \frac{ 1471 }{ 171 } & 1471^2 - 74 \cdot 171^2 = 7 & \mbox{digit} & 1 \\ \frac{ 2228 }{ 259 } & 2228^2 - 74 \cdot 259^2 = -10 & \mbox{digit} & 1 \\ \frac{ 3699 }{ 430 } & 3699^2 - 74 \cdot 430^2 = 1 & \mbox{digit} & 16 \\ \end{array} $$