Generalized Pell's Equation: Why is 4 special?

I know how to generate solutions to $x^2-Dy^2=\pm 1$ from the fundamental solution to $x^2-Dy^2=\pm 4$. But how do we know that all the solutions are generated from this fundamental solution?

-

HINT $\$ The usual descent argument works: $\:$ if $\rm\ x^2-D\:y^2 = 1\$ has fundamental solution $\rm\:\epsilon^k\:$ and $\rm\:\epsilon^n>0\:$ is another solution then $\rm\:k|n\:$ (else $\rm\:\epsilon^{n\ mod\ k}\:$ is a solution smaller than the fundamental one)

If the hint is not detailed enough then you can find full details of this standard argument e.g. in section 1.3 of Jacobson and Williams: Solving the Pell equation. There you'll also find the standard table giving the value of $\rm\ k$ (viz. $\rm\:k|6\:$ and depends on the parity of $\rm x$ and $\rm y$ and the sign of $\pm4)$. Note in particular that the complete proof is not as trivial as the special case in Pete L. Clark's answer.

The reason why "4 is special", i.e. why the equation $\rm\ x^2 - D\:y^2 = \pm 4\$ proves more fundamental than $\rm\ x^2 - D\:y^2 = \pm 1\$ is simply because the former equation is the one that arises when checking that an integer has norm $\pm 1$, i.e. $\rm\ N((x+y\sqrt{D})/2) = \pm1$ iff $\rm\ x^2-D\:y^2 = \pm 4\:$; i.e. the 4 arises from clearing "denominators" in the norm equation.

-
Thank you, Bill. – James Nov 3 '10 at 2:47

I had written out an answer previously, but to make it work I need to assume a little more. Namely, let me assume that $D$ is not congruent to $1 \pmod 4$. (I'll think a little more about what's going on in general, and someone else is of course welcome to jump in and help me out.)

One of the running assumptions of the Pell equation is that $D$ is squarefree. In particular, it is not $0 \pmod 4$. So if you reduce the equation $x^2 - Dy^2 = \pm 4$ modulo $4$, you get $x^2 - Dy^2 \equiv 0 \pmod 4$. Since the squares mod $4$ are $0$ and $1$, running through the four possibilities for $x^2$ and $y^2$ mod $4$ one sees that the only solutions are when $x^2 \equiv y^2 \equiv 0$, i.e., when $x$ and $y$ are even. [N.B.: here I am using that $D \not \equiv 1 \pmod 4$; otherwise $1^2 - D \cdot 1^2 \equiv 0 \pmod 4$.]

That is, every integral solution to $x^2 - Dy^2 = \pm 4$ occurs with $x$ and $y$ even, so we may write $x = 2X$, $y = 2Y$ and substitute, getting

$(2X)^2 - D (2Y)^2 = 4(X^2 - DY^2) = \pm 4$.

Dividing by $4$, we get

$X^2 - DY^2 = \pm 1$.

The process can also be reversed: if $X^2 - DY^2 = \pm 1$, then $(2X)^2 - D(2Y)^2 = \pm 4$. Thus we have found a bijection between the sets of solutions to $x^2 - Dy^2 = \pm 4$ and $X^2 - DY^2 = \pm 1$.

So this is the most direct answer to your question. One can still wonder whether this occurs for integers other than $4$, but for other $k > 1$ it can happen that there are solutions to $x^2 - Dy^2 = \pm k$ in which $x$ and $y$ are not both divisible by $k$. Try it and see. So $4$ is special here because the theory of quadratic equations modulo $4$ is especially simple.

Added: See http://sites.google.com/site/tpiezas/008 for some further information on going from $x^2 - dy^2 = \pm 4$ to $x^2 - dy^2 = \pm 1$.

-
Thank you professor Clark for your clear answer. – James Nov 2 '10 at 21:37