Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

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 ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Open
Bhaskar1312 wants to merge3 commits intocp-algorithms:main
base:main
Choose a base branch
Loading
fromBhaskar1312:GH-1005/pells-eqn

Conversation

@Bhaskar1312
Copy link

@Bhaskar1312Bhaskar1312 commentedNov 1, 2024•
edited
Loading

Proof and how to find using continued fractions.

Chakralava Method
Problems
References

@Bhaskar1312Bhaskar1312 changed the titlePell's equationGH-1005: Pell's equationNov 1, 2024
@adamant-pwn
Copy link
Member

@Bhaskar1312
Copy link
Author

Bhaskar1312 commentedNov 17, 2024•
edited
Loading

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

added in reference section

@Bhaskar1312Bhaskar1312 marked this pull request as ready for reviewNovember 17, 2024 19:37
Copy link
Member

@adamant-pwnadamant-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 toREADME.md andmavigation.md into lists of new articles?

@Bhaskar1312
Copy link
Author

Hi, could you please add this article toREADME.md andmavigation.md into lists of new articles?

added inREADME.md. have I added incorrectly innavigation.md or in incorrect section?

@mhayter
Copy link
Contributor

Updates?

@Bhaskar1312
Copy link
Author

Updated all suggestions. Have I missed any?


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.

Copy link
Author

Choose a reason for hiding this comment

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

Added link to continued fractions and removed floating point based

Copy link
Member

Choose a reason for hiding this comment

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

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.

@Bhaskar1312Bhaskar1312force-pushed theGH-1005/pells-eqn branch 3 times, most recently from271c26a to3f2791eCompareApril 19, 2025 02:46
@Bhaskar1312Bhaskar1312force-pushed theGH-1005/pells-eqn branch 2 times, most recently from22d960e to8f4864bCompareOctober 5, 2025 16:55
Copy link
Member

@adamant-pwnadamant-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, thanks for the updates! I think we should still add some changes to it (see the review).


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$.
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
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$.
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$.

I think we need to disambiguate between$x_0 \pm y_0 \sqrt{d}$. Also, There is no such thing as smallest positive solution, as$x - y \sqrt d$ solutions can be arbitrarily close to$0$, as real numbers.

Additionally, it would be nice to explain why the solution with smallest$x_0 > 1$ and$y_0 > 0$ also produces the minimum possible values of$x_0 + y_0 \sqrt d$.

Copy link
Author

Choose a reason for hiding this comment

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

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

Choose a reason for hiding this comment

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

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

Choose a reason for hiding this comment

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

Should we include a proof to this? I have it onCodeforces, but it's a bit technically involved, I suppose...

Copy link
Author

Choose a reason for hiding this comment

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

Proof is already in method of descent section

d0=1
a0=int(math.isqrt(n))
period= []
m, d, a= m0, d0, a0
Copy link
Member

Choose a reason for hiding this comment

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

It would be nice to add some details on what expression you represent with$m$,$d$ and$a$. I'm used to maintaining the complete quotient as$\frac{x+y\sqrt n}{z}$, but evidently this is not what's happening here...

Copy link
Author

Choose a reason for hiding this comment

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

added recurrence relations


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.

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.

Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment

Reviewers

@adamant-pwnadamant-pwnAwaiting requested review from adamant-pwn

1 more reviewer

@jxujxujxu left review comments

Reviewers whose approvals may not affect merge requirements

Requested changes must be addressed to merge this pull request.

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

4 participants

@Bhaskar1312@adamant-pwn@mhayter@jxu
[8]ページ先頭
©2009-2025 Movatter.jp