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

Question

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?

Answer 1

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.