Skip to content

GH-1005: Pell's equation #1388

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
wants to merge 4 commits into
base: main
Choose a base branch
from

Conversation

Bhaskar1312
Copy link

@Bhaskar1312 Bhaskar1312 commented Nov 1, 2024

Proof and how to find using continued fractions.

Chakralava Method
Problems
References

@Bhaskar1312 Bhaskar1312 changed the title Pell's equation GH-1005: Pell's equation Nov 1, 2024

$$\sf=2+\cfrac{1}{1+\cfrac1{1+\cfrac1{1+\cfrac4{\vdots}}}}$$

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

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Note this relies on floating point numbers. You can do it entirely with integer arithmetic.

Copy link
Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can you give me reference for doing it using integer arithmetic completely?

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

"Quadratic irrationality" section of continued fraction article has it:

# compute the continued fraction of sqrt(n)
def sqrt(n):
    n0 = math.floor(math.sqrt(n))
    x, y, z = 1, 0, 1
    a = []
    def step(x, y, z):
        a.append((x * n0 + y) // z)
        t = y - a[-1]*z
        x, y, z = -z*x, z*t, t**2 - n*x**2
        g = math.gcd(x, math.gcd(y, z))
        return x // g, y // g, z // g

    used = dict()
    for i in range(n):
        used[x, y, z] = i
        x, y, z = step(x, y, z)
        if (x, y, z) in used:
            return a

Copy link
Author

@Bhaskar1312 Bhaskar1312 Nov 17, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

included with a link after non-integer example

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I would actually strongly suggest to replace the whole section to only show integer calculation, as floating-point calculation might be unstable.

@@ -8,5 +8,6 @@ converted.pdf
/public
.firebase/
firebase-debug.log
.idea/
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Do not include this

Copy link
Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

.gitgnore just ignores files to not include them when we do git add .
So, that won't affect anything

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
.idea/

I think we should remove this, unless it is something that is really needed for the project at large, rather than specific developer.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Why is it here again 🤔

@adamant-pwn
Copy link
Member

@Bhaskar1312
Copy link
Author

Bhaskar1312 commented Nov 17, 2024

Possibly useful: Codeforces - Pythagorean triples and Pell's equations.

added in reference section

@Bhaskar1312 Bhaskar1312 marked this pull request as ready for review November 17, 2024 19:37
Copy link
Member

@adamant-pwn adamant-pwn left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Hi, could you please add this article to README.md and mavigation.md into lists of new articles?

@Bhaskar1312
Copy link
Author

Hi, could you please add this article to README.md and mavigation.md into lists of new articles?

added in README.md. have I added incorrectly in navigation.md or in incorrect section?

@Bhaskar1312 Bhaskar1312 requested a review from adamant-pwn March 30, 2025 11:31
@mhayter
Copy link
Contributor

mhayter commented Apr 11, 2025

Updates?

@Bhaskar1312
Copy link
Author

Updated all suggestions. Have I missed any?

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.
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$
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This equation looks like it just comes out of nowhere. As in, it isn't connected with the paragraphs that are immediately adjusted to it. I would add some explanation on what are we doing here exactly.

Also consider wrapping this in $$...$$ instead of $...$.

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.
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

You use the term "norm" here, but it's not defined. We should add a definition + an explanation why we care about it (primarily because it is multiplicative).


$ 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}$.
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We defined the smallest solution by saying that it is the solution with the smallest positive $x$ (but we actually want $x &gt; 1$). It also means that $x + y \sqrt d$ is the smallest possible, of course, but we should mention it explicitly abouve.


## To find the smallest positive solution
### Expressing the solution in terms of continued fractions
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.
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Let's add a link to continued fractions article. Ideally, I would also add explanation on why it is a solution at all, and why is it the smallest possible.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Also, the paragraph says that "the smallest solution is given by ...", but doesn't tell that, specifically, the solution is $p_n^2 - q_n^2 d = 1$. Instead, you just write below that $p_n / q_n$ is the solution.


It can also be calculated using only [integer based calculation](https://cp-algorithms.com/algebra/continued-fractions.html)

### Finding the solution using Chakravala method
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

@Bhaskar1312 Bhaskar1312 force-pushed the GH-1005/pells-eqn branch 2 times, most recently from 2771efd to 271c26a Compare April 19, 2025 02:43
Bhaskar1312 and others added 3 commits April 19, 2025 08:17
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

4 participants