# How to find odd solutions only for Pell's equation $x^2 - Dy^2 = 1$?

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?

-
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
But surely the parity of the $x$’s is periodic, no matter what $D$ is? –  Lubin Sep 17 '12 at 18:49

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