You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: src/others/pells_equation.md
+32-14Lines changed: 32 additions & 14 deletions
Original file line number
Diff line number
Diff line change
@@ -20,18 +20,19 @@ $x^{2} - d \cdot y^{2} = ( x + \sqrt{d} \cdot y ) ( x - \sqrt{d} \cdot y ) = 1$
20
20
21
21
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.
22
22
23
-
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}$.
23
+
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
24
+
$ x_{0} + y_{0} \cdot \sqrt{d} $
24
25
25
-
[//]: #(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)
26
-
[//]: #( $( 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.)
27
-
[//]: #( $(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}$)
26
+
[//]: #(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)
27
+
[//]: #($ ( 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.)
28
+
[//]: #( $(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}$)
[//]: #( 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.)
31
32
[//]: #(First, we prove that product of two solutions is also a solution.)
32
33
33
-
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$
we get the continued fraction of $\sf$ as $[2; 1, 1, 4, 1, 1, 4, \ldots]$.
77
78
79
+
It can also be calculated using only [integer based calculation](https://cp-algorithms.com/algebra/continued-fractions.html)
80
+
78
81
### Finding the solution using Chakravala method
79
-
The Chakravala method is an ancient Indian algorithm to solve Pell's equation. It is based on the Brahmagupta's identity of quadratic decomposition.
82
+
The Chakravala method is an ancient Indian algorithm to solve Pell's equation. It is based on the Brahmagupta's identity of quadratic decomposition
80
83
$(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}$
81
84
$(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}$
82
85
86
+
And Bhaskara's Lemma:
87
+
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}$
88
+
83
89
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}$
84
90
85
-
[//]: #(First, we choose $y_{1} = 1$ and choose $x_{1} = \lfloor \sqrt n \rfloor$ such that $k_{1}$ is a small integer.)
91
+
#### Steps
92
+
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 $.
93
+
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.
3. Termination: When $m_{k}=1$, the values of $p_{k}$ and $q_{k}$ are the smallest positive solution of the Pell's equation.
96
+
97
+
##### Example
98
+
Let's solve the equation $x^{2} - 13 \cdot y^{2} = 1$ using Chakravala method.
99
+
1. Start with $(p_{0}, q_{0}, m_{0}) = (3, 1, -4)$ because $3^2 - 13 \cdot1^2 = -4$.
86
100
87
-
[//]: #()
88
-
[//]: #(Then, Iteratively we adjust $x_{1}$ and $y_{1}$ so that $k_{1} = 1$. The solution is given by $(x_{1}, y_{1})$ to original Pell's equation.)
89
-
[//]: #()
90
-
[//]: #( Choosing m. At e)
101
+
2. Find $x_{1}$ such that $x_{1} \equiv -3 \pmod {4}$ and $\lvert x_{1}^2 - 13 \rvert$ is minimized.
0 commit comments