Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How can I find only the odd solutions for Pell's equation: $$x^2 - Dy^2 = 1$$ Specifically where $x$ is odd (but $y$ may be even or odd).
Is there a way to generate the odd solutions to $x$, and can they be finite?

share|improve this question
1  
What is wrong with generating all the solutions, and then disregarding the ones where $x$ is even? –  Aaron Sep 17 '12 at 18:32
    
@Aaron but aren't there infinite number of solutions ?? thus I cannot know when to stop and whether there will be a new odd solution on a specific interval . –  Loers Antario Sep 17 '12 at 18:35
2  
But surely the parity of the $x$’s is periodic, no matter what $D$ is? –  Lubin Sep 17 '12 at 18:49
add comment

1 Answer

up vote 6 down vote accepted

By the standard algorithm for solving Pells equation, you find a linear recurrence for the $n$-th solution $x_n, y_n$. These formulas are not too difficult to work out by hand, and originate from $x_n + \sqrt{D}y_n = (x_1+\sqrt{D}y_1)^n$ where $x_1,y_1$ is the basic solution. The resulting formula seems to be: $$ x_{n} = a x_{n-1} + D b y_{n-1} \\ y_{n} = a y_{n-1} + b x_{n-1} $$ where $(a,b) = (x_1,y_1)$.

This in particular means that parity of $x_{n+1},y_{n+1}$ is determined only by parity of $x_n, y_n$. Thus, the parity is periodic, with period at most $4$. You can just write down the lowest couple of solutions, and use this to determine how long the period is, and which terms you need to select. If $x_n,y_n$ is the first pair with the same parity as $x_1,y_1$, then the period is just $n-1$, and the solutions with $x$ odd are just these of the form $k (n-1) + m$ with $k$ is an integer and $1 \leq m < n$ such that $x_m$ is odd. In particular, either $x$ is never odd, or it is odd infinitely often.

share|improve this answer
2  
In fact, it's pretty easy to see that $x_2=x_1^2+Dy_1^2$ is always odd, and $y_2=2x_1y_1$ is clearly always even. So the period is at most 2. –  Micah Sep 17 '12 at 21:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.