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
+9-4Lines changed: 9 additions & 4 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -22,16 +22,21 @@ This factorization is important because it shows the connection to quadratic irr
22
22
23
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
24
25
-
We will prove that all solutions to Pell's equation are given by powers of the smallestpositive solution. Let's assume it to be $x_0 + y_0 \sqrt{d}$, where $x_0 > 1$ is the smallest possible value for $x$.
25
+
We will prove that all solutions to Pell's equation are given by powers of the smallestnon-trivial solution. Let's assume it to bethe minimum possible$x_0 + y_0 \sqrt{d} > 1$. For such a solution, it also holds that $y_0 > 0$, and its $x_0 > 1$ is the smallest possible value for $x$.
26
26
27
27
##Method of Descent
28
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} )$
29
29
Then it must lie between two powers of $( x_{0} + \sqrt{d} \cdot y_{0} )$.
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}$
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.
36
41
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}$.