/public

.firebase/

.idea/

-[Scheduling jobs on two machines](schedules/schedule_two_machines.md)

-[Optimal schedule of jobs given their deadlines and durations](schedules/schedule-with-completion-duration.md)

- Miscellaneous

-[Pell's Equation](others/pells_equation.md)

-[Tortoise and Hare Algorithm (Linked List cycle detection)](others/tortoise_and_hare.md)

-[Josephus problem](others/josephus_problem.md)

-[15 Puzzle Game: Existence Of The Solution](others/15-puzzle.md)

tags:

-Original

We are given a natural number $d$. We need to find the smallest positive integer $x$ such that $x^{2} - d \cdot y^{2} = 1$ for some integer $y$.

OR

We want to find all the possible solutions of the equation $x^{2} - d \cdot y^{2} = 1$.

Here we will consider the case when $d$ is not a perfect square and $d>1$. The case when $n$ is a perfect square is trivial.

We can even assume that $d$ is square-free (i.e. it is not divisible by the square of any prime number) as we can absorb the factors of $d$ into y.

$x^{2} - d \cdot y^{2} = ( x + \sqrt{d} \cdot y ) ( x - \sqrt{d} \cdot y ) = 1$

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 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}$

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

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

Because both $(u + v \cdot \sqrt{d})$ and $( x_{0} - \sqrt{d} \cdot y_{0} )^{n}$ have norm 1, their product is also a solution.

But this contradicts our assumption that $( x_{0} + \sqrt{d} \cdot y_{0} )$ is the smallest solution. Therefore, there is no solution between $( x_{0} + \sqrt{d} \cdot y_{0} )^{n}$ and $( x_{0} + \sqrt{d} \cdot y_{0} )^{n+1}$.

Hence, we conclude that all solutions are given by $( x_{0} + \sqrt{d} \cdot y_{0} )^{n}$ for some integer $n$.

We can express the solution in terms of continued fractions. The continued fraction of $\sqrt{d}$ is periodic. Let's assume the continued fraction of $\sqrt{d}$ is $[a_{0}; \overline{a_{1}, a_{2}, \ldots, a_{r}}]$. The smallest positive solution is given by the convergent $[a_{0}; a_{1}, a_{2}, \ldots, a_{r}]$ where $r$ is the period of the continued fraction.

The convergents $p_{n}/q_{n}$ are the rational approximations to $\sqrt{d}$ obtained by truncating the continued fraction expansion at each stage. These convergents can be computed recursively.

Check whether the convergent satisfies the Pell's equation. If it does, then the convergent is the smallest positive solution.

Let's take an example to understand this by solving the equation $x^{2} - 2 \cdot y^{2} = 1$.

$\sqrt{2} =[1; \overline{2}] = 1 + 1/(2 + 1/(2 + 1/(2+ ...))) $. The convergents are $1/1, 3/2, 7/5, 17/12, 41/29, 99/70, \ldots$.

Now check for each convergent whether it satisfies the Pell's equation. The smallest positive solution is $3/2$.

Let's find the continued fraction of $\def\sf{\sqrt 7}\sf$.

$\sf \approx 2.6457 = 2 + 0.6457$

$a_{0} = 2 $

Subtract $a_{0}$ from the number and take the reciprocal of the remaining number.

That is, we calculate ${1\over \sf - 2} \approx 1.5486$. The integer part $a_{1}$ is $1$.

So:

$$\sf=2+\cfrac{1}{1+\cfrac1{\vdots}}$$ Where we haven't calculated the $\vdots$ part yet.

To get that, we subtract $a_{1}$ from the number and take the reciprocal of the remaining number. That is, we calculate ${1\over 1.5486 - 1} \approx 1.8228$. The integer part $a_{2}$ is $1$.

So:

Now ${1\over 1.8228 - 1} \approx 1.2153$. So $a_{3} = 1$.

Continuing this process, ${1\over 1.2153 - 1} \approx 4.645$. So $a_{4} = 4$.

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