Register to reply

Recurrence formula in Pell's equation

by basil
Tags: equation, formula, pell, recurrence
Share this thread:
basil
#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
'Smart material' chin strap harvests energy from chewing
King Richard III died painfully on battlefield
Capturing ancient Maya sites from both a rat's and a 'bat's eye view'
phinds
#2
Jun14-11, 08:18 AM
PF Gold
phinds's Avatar
P: 6,497
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
#3
Jun14-11, 10:41 AM
P: 96
It works with: X^2 - 2*Y^2 = 1

disregardthat
#4
Jun14-11, 12:45 PM
Sci Advisor
P: 1,810
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
#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
#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
#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