5
$\begingroup$

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?

  • 3
    But surely the parity of the $x$’s is periodic, no matter what $D$ is?2012-09-17

2 Answers 2

6

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.

  • 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.2012-09-17
0
  • First of all notice that if $D$ is even (and $x,y \in \mathbb{Z}$), then $x^2 = D y^2 + 1$ is odd, and therefore $x$ is always odd and $y$ is always even.

  • On the other hand, if $D$ is odd, we can only have:

    1) $x_1$ even and $y_1$ odd, or

    2) $x_1$ odd and $y_1$ even,

    where $(x_1, y_1)$ is the fundamental solution.

    The recurrence formula for the $n$-th solution is: \begin{align} x_{n} &= x_1 x_{n-1} + D y_1 y_{n-1}\\ y_{n} &= x_1 y_{n-1} + y_1 x_{n-1} \end{align} Therefore, if $x_1$ is even and $y_1$ is odd, then $x_{n}$ is even (odd) and $y_{n}$ is odd (even) if $x_{n-1}$ is odd (even) and $y_{n-1}$ is even (odd). That is, $x_2$ is odd and $y_2$ is even, $x_3$ is even and $y_3$ is odd etc. So we have oscillation of the parity with period equal to 2.

    Otherwise, if $x_1$ is odd and $y_1$ is even, then $x_{n}$ is odd and $y_{n}$ is even, $\forall n$.