GH-1005: Pell's equation #1388
GH-1005: Pell's equation #1388
Conversation
Bhaskar1312
force-pushed
the
GH-1005/pells-eqn
branch
from
79f7120 to
a4c3729
Compare
|
Possibly useful: Codeforces - Pythagorean triples and Pell's equations. |
Bhaskar1312
force-pushed
the
GH-1005/pells-eqn
branch
from
db59072 to
4732ab4
Compare
added in reference section |
Bhaskar1312
force-pushed
the
GH-1005/pells-eqn
branch
from
123711e to
bd4351c
Compare
adamant-pwn
left a comment
adamant-pwn
left a comment
There was a problem hiding this comment.
Hi, could you please add this article to README.md and mavigation.md into lists of new articles?
Bhaskar1312
force-pushed
the
GH-1005/pells-eqn
branch
from
f88828b to
c72a19c
Compare
added in |
|
Updates? |
|
Updated all suggestions. Have I missed any? |
Bhaskar1312
force-pushed
the
GH-1005/pells-eqn
branch
from
ab10315 to
5ff3016
Compare
Bhaskar1312
force-pushed
the
GH-1005/pells-eqn
branch
from
5ff3016 to
32e048b
Compare
|
|
||
| It can also be calculated using only [integer based calculation](https://cp-algorithms.com/algebra/continued-fractions.html) | ||
|
|
||
| ### Finding the solution using Chakravala method |
There was a problem hiding this comment.
This looks complicated. Are there specific reasons to do it over continued fractions variant? I find the exposition very hard to read (largely because of misrenders, though).
Unless it's in some way better than continued fractions method, I'd consider dropping the section altogether.
There was a problem hiding this comment.
Added link to continued fractions and removed floating point based
There was a problem hiding this comment.
Thanks! But I'm still not convinced this section is needed at all. It seems much more complicated than doing it with convergents. I really think we should either have a good reason to include it (e.g. mention why is it better than convergents), or remove it.
Bhaskar1312
force-pushed
the
GH-1005/pells-eqn
branch
3 times, most recently
from
271c26a to
3f2791e
Compare
Bhaskar1312
force-pushed
the
GH-1005/pells-eqn
branch
2 times, most recently
from
22d960e to
8f4864b
Compare
adamant-pwn
left a comment
adamant-pwn
left a comment
There was a problem hiding this comment.
Hi, thanks for the updates! I think we should still add some changes to it (see the review).
src/others/pells_equation.md
Outdated
|
|
||
| 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. | ||
|
|
||
| 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$. |
There was a problem hiding this comment.
| 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$. | |
| We will prove that all solutions to Pell's equation are given by powers of the smallest non-trivial solution. Let's assume it to be the 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$. |
I think we need to disambiguate between
Additionally, it would be nice to explain why the solution with smallest
There was a problem hiding this comment.
This is given in equations in method of descent section
|
|
||
| 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$. | ||
|
|
||
| Check whether the convergent satisfies Pell's equation. If it does, then the convergent is the smallest positive solution. |
There was a problem hiding this comment.
We should also write what happens if it doesn't...
| Hence, we conclude that all solutions are given by $( x_{0} + \sqrt{d} \cdot y_{0} )^{n}$ for some integer $n$. | ||
|
|
||
| ## Finding the smallest positive solution | ||
| ### Expressing the solution in terms of continued fractions |
There was a problem hiding this comment.
Should we include a proof to this? I have it on Codeforces, but it's a bit technically involved, I suppose...
There was a problem hiding this comment.
Proof is already in method of descent section
| d0 = 1 | ||
| a0 = int(math.isqrt(n)) | ||
| period = [] | ||
| m, d, a = m0, d0, a0 |
There was a problem hiding this comment.
It would be nice to add some details on what expression you represent with
|
|
||
| It can also be calculated using only [integer based calculation](https://cp-algorithms.com/algebra/continued-fractions.html) | ||
|
|
||
| ### Finding the solution using Chakravala method |
There was a problem hiding this comment.
Thanks! But I'm still not convinced this section is needed at all. It seems much more complicated than doing it with convergents. I really think we should either have a good reason to include it (e.g. mention why is it better than convergents), or remove it.
Bhaskar1312
force-pushed
the
GH-1005/pells-eqn
branch
from
9cf13e5 to
eea90be
Compare
Bhaskar1312
force-pushed
the
GH-1005/pells-eqn
branch
from
eea90be to
982d59e
Compare
4 participants
Proof and how to find using continued fractions.
Chakralava Method
Problems
References