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?

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