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
+40-34Lines changed: 40 additions & 34 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -14,14 +14,17 @@ Alternative formulation: We want to find all the possible solutions of the equat
14
14
Here we will consider the case when $d$ is not a perfect square and $d>1$. The case when $d$ is a perfect square is trivial.
15
15
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$.
16
16
17
-
$x^{2} - d \cdot y^{2} = ( x + \sqrt{d} \cdot y ) ( x - \sqrt{d} \cdot y ) = 1$
17
+
We can rewrite the equation as:
18
18
19
-
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, since the product is 1.
19
+
$$x^{2} - d y^{2} = (x + y \sqrt{d})(x - y \sqrt{d}) = 1$$
20
20
21
-
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
22
-
$x_{0} + y_{0} \cdot \sqrt{d}$
21
+
This factorization is important because it shows the connection to quadratic irrationals. The first part $(x + y \sqrt{d})$ is always greater than 1, and the second part $(x - y \sqrt{d})$ is always less than 1, since their product is 1.
23
22
24
-
We use method of descent to prove it.
23
+
The norm of an expression $u + v \sqrt{d}$ is defined as $N(u + v \sqrt{d}) = (u + v \sqrt{d})(u - v \sqrt{d}) = u^2 - d v^2$. The norm is multiplicative: $N(ab) = N(a)N(b)$. This property is crucial in the descent argument below.
24
+
25
+
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 \sqrt{d}$, where $x_0 > 1$ is the smallest possible value for $x$.
26
+
27
+
## Method of Descent
25
28
Suppose there is a solution $u + v \cdot \sqrt{d}$ such that $u^{2} - d \cdot v^{2} = 1$ and is not a power of $( x_{0} + \sqrt{d} \cdot y_{0} )$
26
29
Then it must lie between two powers of $( x_{0} + \sqrt{d} \cdot y_{0} )$.
27
30
i.e, For some n, $( x_{0} + \sqrt{d} \cdot y_{0} )^{n} < u + v \cdot \sqrt{d} < ( x_{0} + \sqrt{d} \cdot y_{0} )^{n+1}$
@@ -36,40 +39,43 @@ Hence, we conclude that all solutions are given by $( x_{0} + \sqrt{d} \cdot y_{
36
39
37
40
## Finding the smallest positive solution
38
41
### Expressing the solution in terms of continued fractions
39
-
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.
42
+
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.
40
43
41
-
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.
44
+
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. For Pell's equation, the convergent $(p_n, q_n)$ at the end of the period solves $p_n^2 - d q_n^2 = \pm 1$.
42
45
43
-
Check whether the convergent satisfies the Pell's equation. If it does, then the convergent is the smallest positive solution.
46
+
Check whether the convergent satisfies Pell's equation. If it does, then the convergent is the smallest positive solution.
44
47
45
-
Let's take an example to understand this by solving the equation $x^{2} - 2 \cdot y^{2} = 1$.
48
+
Let's take an example to understand this by solving the equation $x^2 - 2 y^2 = 1$.
Now check for each convergent whether it satisfies the Pell's equation. The smallest positive solution is $3/2$.
48
-
49
-
### How to calculate the continued fraction of $\sqrt{d}$?
50
-
Let's find the continued fraction of $\sqrt{7}$.
51
-
52
-
$\sqrt{7} \approx 2.6457 = 2 + 0.6457$
53
-
54
-
$a_{0} = 2$
55
-
56
-
Subtract $a_{0}$ from the number and take the reciprocal of the remaining number.
57
-
58
-
That is, we calculate ${1\over \sqrt{7} - 2} \approx 1.5486$. The integer part $a_{1}$ is $1$.
59
-
So:
60
-
$\sqrt{7}=2+\cfrac{1}{1+\cfrac1{\vdots}}$
61
-
Where we haven't calculated the $( \vdots )$ part yet.
62
-
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$.
we get the continued fraction of $\sqrt{7}$ as $[2; 1, 1, 4, 1, 1, 4, \ldots]$.
50
+
Now check for each convergent whether it satisfies Pell's equation. The smallest positive solution is $3/2$.
51
+
52
+
#### Integer-based continued fraction calculation
53
+
For integer-based calculation, see the [Quadratic irrationality section of the continued fractions article](https://cp-algorithms.com/algebra/continued-fractions.html). Here is a sample algorithm in Python:
54
+
55
+
```python
56
+
# Compute the continued fraction expansion of sqrt(n) using integer arithmetic
0 commit comments