Register to reply 
Recurrence formula in Pell's equation 
Share this thread: 
#1
Jun1411, 07:40 AM

P: 8

Hello,
I am trying to solve a Pell's equation X^{2} + 2Y^{2} =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? 


#2
Jun1411, 08:18 AM

PF Gold
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?



#3
Jun1411, 10:41 AM

P: 96

It works with: X^2  2*Y^2 = 1



#4
Jun1411, 12:45 PM

Sci Advisor
P: 1,810

Recurrence formula in Pell's equation
The equation is (xsqrt(2)y)(x+sqrt(2)y) = 1. Now, your solution is (3,2), so (3sqrt(2)2)(3+sqrt(2)2) = 1, and by multiplying we have 1 = (xsqrt(2)y)(3sqrt(2)2)(x+sqrt(2)y)(3+sqrt(2)2) = (3x+4y(2x+3y)sqrt(2))(3x+4y+(2x+3y)sqrt(2)) = (3x+4y)^22(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.) 


#5
Jun1611, 07:17 AM

P: 8

Hey,
Yep its my mistake. Its supposed to be x^{2}y^{2}=1 Thanks for pointing out. 


#6
Jun1611, 07:18 AM

P: 8




#7
Jun1911, 10:47 AM

P: 96

Let x[itex]_{1}[/itex], y[itex]_{1}[/itex] be basic solutions to
x^2N*y^2 = 1, with N a nonsquare 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 nontrivial 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 