The first part $( x + \sqrt{d} \cdot y )$ is always greater than 1. And the second part $( x - \sqrt{d} \cdot y )$ is always less than 1.

We will prove that all solutions to Pell's equation are given by powers of the smallest positive solution. Let's assume it to be $ x_{0} + y_{0} \cdot \sqrt{d}$.

We will prove that all solutions to Pell's equation are given by powers of the smallest positive solution. Let's assume it to be

$ x_{0} + y_{0} \cdot \sqrt{d} $

[//]:#(We claim that every solution to the equation is given by $(x_{0} + y_{0} \cdot \sqrt{d})^{n}$ for some integer $n$. The idea is that any other solution)

[//]:#( $( x + \sqrt{d} \cdot y)$ must be of this form, meaning that all solutions are generated by repeated multiplication of the smallest solution. Here we use Brahmagupta's identity of quadratic decomposition.)

[//]:#( $(a^{2} - n \cdot b^{2}) \cdot(c^{2} - n \cdot d^{2}) =(a \cdot c + n \cdot b \cdot d)^{2} - n \cdot(a \cdot d + b \cdot c)^{2}$)

[//]:#(We claim that every solution to the equation is given by $(x_{0} + y_{0} \cdot \sqrt{d})^{n}$ for some integer $ n$. The idea is that any other solution)

[//]:#($( x + \sqrt{d} \cdot y)$ must be of this form, meaning that all solutions are generated by repeated multiplication of the smallest solution. Here we use Brahmagupta's identity of quadratic decomposition.)

[//]:#( $(a^{2} - n \cdot b^{2}) \cdot(c^{2} - n \cdot d^{2}) =(a \cdot c + n \cdot b \cdot d)^{2} - n \cdot(a \cdot d + b \cdot c)^{2}$)

[//]:#()

[//]:#(Here, $a = x_{1}$, $b = y_{1}$, $c = x_{2}$, $d = y_{2}$)

[//]:#( So if(x_{1}, y_{1}) and(x_{2}, y_{2}) are solutions, then $(x_{1} \cdot x_{2} + n \cdot y_{1} \cdot y_{2}, x_{1} \cdot y_{2} + y_{1} \cdot x_{2})$ is also a solution.)

[//]:#(First, we prove that product of two solutions is also a solution.)

We use method of descent to prove it. suppose there is a solution $u + v \cdot \sqrt{d}$ such that $u^{2} - d \cdot v^{2} = 1$

Therefore, $ ( x_{0} + \sqrt{d} \cdot y_{0} )^{n} < u + v \cdot \sqrt{d} < ( x_{0} + \sqrt{d} \cdot y_{0} )^{n+1}$

We use method of descent to prove it. suppose there is a solution $u + v \cdot \sqrt{d}$ such that $u^{2} - d \cdot v^{2} = 1$

Therefore, $ ( x_{0} + \sqrt{d} \cdot y_{0} )^{n} < u + v \cdot \sqrt{d} < ( x_{0} + \sqrt{d} \cdot y_{0} )^{n+1}$

Multiplying the above inequality by $( x_{0} - \sqrt{d} \cdot y_{0} )^{n}$,(which is > 0 and < 1) we get

we get the continued fraction of $\sf$ as $[2; 1, 1, 4, 1, 1, 4, \ldots]$.

It can also be calculated using only[integer based calculation](https://cp-algorithms.com/algebra/continued-fractions.html)

The Chakravala method is an ancient Indian algorithm to solve Pell's equation. It is based on the Brahmagupta's identity of quadratic decomposition.

The Chakravala method is an ancient Indian algorithm to solve Pell's equation. It is based on the Brahmagupta's identity of quadratic decomposition

$(x_{1}^{2} - n \cdot y_{1}^{2}) \cdot (x_{2}^{2} - n \cdot y_{2}^{2}) = (x_{1} \cdot x_{2} + n \cdot y_{1} \cdot y_{2})^{2} - n \cdot (x_{1} \cdot y_{2} + x_{2} \cdot y_{1})^{2}$

$(x_{1}^{2} - n \cdot y_{1}^{2}) \cdot (x_{2}^{2} - n \cdot y_{2}^{2}) = (x_{1} \cdot x_{2} - n \cdot y_{1} \cdot y_{2})^{2} - n \cdot (x_{1} \cdot y_{2} - x_{2} \cdot y_{1})^{2}$

And Bhaskara's Lemma:

If $x^{2} - n \cdot y^{2} = k$, then $ ( \frac{ m \cdot x + n \cdot y }{k})^{2} - n \cdot ( \frac{ x + m \cdot y }{k})^{2} = \frac{m^2 - n}{k}$

Using above Brahmagupta's identity, If $(x_{1}, y_{1}, k_{1})$ and $(x_{2}, y_{2}, k_{2})$ satisfy $(x_{1}^{2} - y_1^{2}) \cdot (x_{2}^{2} - y_2^{2}) = k_{1} \cdot k_{2} $, then $(x_{1} \cdot x_{2} + n \cdot y_{1} \cdot y_{2}, x_{1} \cdot y_{2} + y_{1} \cdot x_{2}, k_{1} \cdot k_{2})$ is also a solution of $(x_{1} \cdot x_{2} + n \cdot y_{1} \cdot y_{2})^{2} - n \cdot (x_{1} \cdot y_{2} + x_{2} \cdot y_{1})^{2} = k_{1} \cdot k_{2}$

[//]:#(First, we choose $y_{1} = 1$ and choose $x_{1} = \lfloor \sqrt n \rfloor$ such that $k_{1}$ is a small integer.)

1. Initialization:Choose an initial solution $(p_{0}, q_{0}, m_{0})$ where $p_{0}$ and $q_{0}$ are co-prime such that $p_{0}^{2} - N \cdot q_{0}^{2} = m_{0}$. Typically, start with $p_{0} = \lfloor \sqrt N \rfloor $, $q_{0} = 1$, $m_{0} = p_0^2 - N $.

2. Key step: Find $x_{1}$ such that: $q_{0} \cdot x_{1} \equiv -p_{0} \pmod {\lvert m_{0}\rvert}$ and $\lvert x_{1}^2 - N \rvert$ is minimized.

Update the triple $(p_{1}, q_{1}, m_{1}) = ( \frac{x_{1} \cdot p_{0} + N \cdot q_{0}}{\lvert m_{0} \rvert}, \frac{p_{0} + x_{1} \cdot q_{0}}{\lvert m_{0} \rvert}, \frac{x_1^{2} - N}{m_{0}})$.

3. Termination: When $m_{k}=1$, the values of $p_{k}$ and $q_{k}$ are the smallest positive solution of the Pell's equation.

Let's solve the equation $x^{2} - 13 \cdot y^{2} = 1$ using Chakravala method.

1. Start with $(p_{0}, q_{0}, m_{0}) = (3, 1, -4)$ because $3^2 - 13 \cdot1^2 = -4$.

[//]:#()

[//]:#(Then, Iteratively we adjust $x_{1}$ and $y_{1}$ so that $k_{1} = 1$. The solution is given by $&#40;x_{1}, y_{1}&#41;$ to original Pell's equation.)

[//]:#()

[//]:#( Choosing m. At e)

2. Find $x_{1}$ such that $x_{1} \equiv -3 \pmod {4}$ and $\lvert x_{1}^2 - 13 \rvert$ is minimized.

We get $x_{1} = 1$. Update the triple $(p_{1}, q_{1}, m_{1}) = ( \frac{1 \cdot 3 + 13 \cdot 1}{4}, \frac{3 + 1 \cdot 1}{4}, \frac{1^{2} - 13}{-4}) = (4, 1, 3)$.

3. Substituting $(p_{1}, q_{1}, k_{1}) = (4, 1, 3)$ in key step, we get $x_{2} \equiv -4 \pmod 3$ and minimize $\lvert x_{2}^2 - 13 \rvert$ i.e, $x_{2} = 2$. Update the triple $(p_{2}, q_{2}, m_{2}) = ( \frac{2 \cdot 4 + 13 \cdot 1}{3}, \frac{4 + 2 \cdot 1}{3}, \frac{2^{2} - 13}{-3}) = (7, 2, -3)$.

4. Substituting $(p_{2}, q_{2}, m_{2}) = (7, 2, -3)$ in key step, we get $2 \cdot x_{3} \equiv -7 \pmod 3$ and minimize $\lvert x_{3}^2 - 13 \rvert$ i.e, $x_{3} = 4$. Update the triple $(p_{3}, q_{3}, m_{3}) = ( \frac{4 \cdot 7 + 13 \cdot 2}{3}, \frac{7 + 4 \cdot 2}{3}, \frac{4^{2} - 13}{-3}) = (18, 5, -1)$.

5. Substituting $(p_{3}, q_{3}, m_{3}) = (18, 5, -1)$ in key step, we get $5 \cdot x_{4} \equiv -18 \pmod 1$ and minimize $\lvert x_{4}^2 - 13 \rvert$ i.e, $x_{4} = 4$. Update the triple $(p_{4}, q_{4}, m_{4}) = ( \frac{4 \cdot 18 + 13 \cdot 5}{1}, \frac{18 + 4 \cdot 5}{1}, \frac{4^{2} - 13}{-1}) = (137, 38, -3)$.

6. Substituting $(p_{4}, q_{4}, m_{4}) = (137, 38, -3)$ in key step, we get $ 38 \cdot x_{5} \equiv -137 \pmod 3$ and minimize $\lvert x_{5}^2 - 13 \rvert$ i.e, $x_{5} = 2$. Update the triple $(p_{5}, q_{5}, m_{5}) = ( \frac{2 \cdot 137 + 13 \cdot 38}{3}, \frac{137 + 2 \cdot 38}{3}, \frac{2^{2} - 13}{-3}) = (256, 71, 3)$.

7. Substituting $(p_{5}, q_{5}, m_{5}) = (256, 71, 3)$ in key step, we get $ 71 \cdot x_{6} \equiv -256 \pmod 3$ and minimize $\lvert x_{6}^2 - 13 \rvert$ i.e, $x_{6} = 4$. Update the triple $(p_{6}, q_{6}, m_{6}) = ( \frac{4 \cdot 256 + 13 \cdot 71}{3}, \frac{256 + 4 \cdot 71}{3}, \frac{4^{2} - 13}{3}) = (649, 180, 1)$.

-[Pell's equation - Wikipedia](https://en.wikipedia.org/wiki/Pell%27s_equation)

-[Periodic Continued Fractions](https://en.wikipedia.org/wiki/Periodic_continued_fraction)

-[Chakralava Method - Wikipedia](https://en.wikipedia.org/wiki/Chakravala_method)

-[Chakralava Method](https://www.isibang.ac.in/~sury/chakravala.pdf)

-[Chakravala Method - Wikipedia](https://en.wikipedia.org/wiki/Chakravala_method)

-[Chakravala Method](http://publications.azimpremjifoundation.org/1630/1/3_The%20Chakravala%20Method.pdf)

-[Chakravala Method](https://www.isibang.ac.in/~sury/chakravala.pdf)

-[Codeforces Pell's Equation](https://codeforces.com/topic/116937/en20)