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 merge4 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

$$\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 ofcontinued fraction article has it:

# compute the continued fraction of sqrt(n)defsqrt(n):n0=math.floor(math.sqrt(n))x,y,z=1,0,1a= []defstep(x,y,z):a.append((x*n0+y)//z)t=y-a[-1]*zx,y,z=-z*x,z*t,t**2-n*x**2g=math.gcd(x,math.gcd(y,z))returnx//g,y//g,z//gused=dict()foriinrange(n):used[x,y,z]=ix,y,z=step(x,y,z)if (x,y,z)inused:returna

Copy link
Author

@Bhaskar1312Bhaskar1312Nov 17, 2024•
edited
Loading

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 dogit 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 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?

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

@Bhaskar1312Bhaskar1312force-pushed theGH-1005/pells-eqn branch 2 times, most recently from2771efd to271c26aCompareApril 19, 2025 02:43
Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment
Reviewers

@jxujxujxu left review comments

@adamant-pwnadamant-pwnadamant-pwn requested changes

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