Recurrence formula in Pell's equation


by basil
Tags: equation, formula, pell, recurrence
basil
basil is offline
#1
Jun14-11, 07:40 AM
P: 8
Hello,

I am trying to solve a Pell's equation

X2 + 2Y2 =1

I understand that the (3,2) is a fundamental solution to the equation. However, I am having difficulty to obtain the recurrence formula in order to generate further solutions. Can anybody help?
Phys.Org News Partner Science news on Phys.org
Review: With Galaxy S5, Samsung proves less can be more
Making graphene in your kitchen
Study casts doubt on climate benefit of biofuels from corn residue
phinds
phinds is offline
#2
Jun14-11, 08:18 AM
PF Gold
phinds's Avatar
P: 5,693
I don't know anything about this, but I do question how you can get (3,2) as a solution to x^2 + 2*y^2 = 1, since I get 3^2 + 2*2^2 = 17 which is most emphatically not 1. What am I missing?
RamaWolf
RamaWolf is offline
#3
Jun14-11, 10:41 AM
P: 96
It works with: X^2 - 2*Y^2 = 1

disregardthat
disregardthat is offline
#4
Jun14-11, 12:45 PM
Sci Advisor
P: 1,690

Recurrence formula in Pell's equation


The equation is (x-sqrt(2)y)(x+sqrt(2)y) = 1. Now, your solution is (3,2), so (3-sqrt(2)2)(3+sqrt(2)2) = 1, and by multiplying we have 1 = (x-sqrt(2)y)(3-sqrt(2)2)(x+sqrt(2)y)(3+sqrt(2)2) = (3x+4y-(2x+3y)sqrt(2))(3x+4y+(2x+3y)sqrt(2)) = (3x+4y)^2-2(2x+3y)^2. Hence if we denote (3,2) by (x_0,y_0), you can define (x_{n+1},y_{n+1}) = (3x_n+4y_n,2x_n+3y_n), and thus (x_n,y_n) will be a solution for each n.

Now, we have found some solutions, but is this all? It is a good exercise to prove this.

Hint: (Suppose (x,y) is a solution not in the sequence defined above, and use the recurrence formula backwards to find the "least" positive solution. (a,b) is the "least" solution if a+b is minimal. Try to find a contradiction.)
basil
basil is offline
#5
Jun16-11, 07:17 AM
P: 8
Hey,

Yep its my mistake. Its supposed to be

x2-y2=1

Thanks for pointing out.
basil
basil is offline
#6
Jun16-11, 07:18 AM
P: 8
Quote Quote by disregardthat View Post
The equation is (x-sqrt(2)y)(x+sqrt(2)y) = 1. Now, your solution is (3,2), so (3-sqrt(2)2)(3+sqrt(2)2) = 1, and by multiplying we have 1 = (x-sqrt(2)y)(3-sqrt(2)2)(x+sqrt(2)y)(3+sqrt(2)2) = (3x+4y-(2x+3y)sqrt(2))(3x+4y+(2x+3y)sqrt(2)) = (3x+4y)^2-2(2x+3y)^2. Hence if we denote (3,2) by (x_0,y_0), you can define (x_{n+1},y_{n+1}) = (3x_n+4y_n,2x_n+3y_n), and thus (x_n,y_n) will be a solution for each n.

Now, we have found some solutions, but is this all? It is a good exercise to prove this.

Hint: (Suppose (x,y) is a solution not in the sequence defined above, and use the recurrence formula backwards to find the "least" positive solution. (a,b) is the "least" solution if a+b is minimal. Try to find a contradiction.)
Awesome. Thanks heaps.
RamaWolf
RamaWolf is offline
#7
Jun19-11, 10:47 AM
P: 96
Let x[itex]_{1}[/itex], y[itex]_{1}[/itex] be basic solutions to

x^2-N*y^2 = 1, with N a non-square integer number

then we have the following recurrence relations for k>1:

x[itex]_{k+1}[/itex]:=x[itex]_{1}[/itex]*x[itex]_{k}[/itex]+N*y[itex]_{1}[/itex]*y[itex]_{k}[/itex]
y[itex]_{k+1}[/itex]:=x[itex]_{1}[/itex]*y[itex]_{k}[/itex]+y[itex]_{1}[/itex]*x[itex]_{k}[/itex]

For N=2, (2,3) being the basic solution, we have (17,12) as 2. and (99,70) as 3.solution

A trivial algorithm to find the basic solution could be:

y:=1, max:=999
Do While n < max
[itex]\cdots[/itex]Compute w=1+N*y^2
[itex]\cdots[/itex]If w is an integral square x^2 then
[itex]\cdots\cdots[/itex]Return "Basic solution: (x, y)" and Stop
[itex]\cdots[/itex]End_If
[itex]\cdots[/itex]Incr y
End_Do
Return max & " trials and no solution" and Stop

Because there are values of N, whrer this "Q&D"-algorithm fails,
who has experience with with non-trivial algorithms for basic solutions
to the Pell equation?


Register to reply

Related Discussions
Pell's Equation Linear & Abstract Algebra 4
Question related to Pell's Equation Linear & Abstract Algebra 7
Generalized Pell Equation and Primes Linear & Abstract Algebra 6
How to solve Pell's equation Linear & Abstract Algebra 10
Reducing to Pell's equation. Linear & Abstract Algebra 4