Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
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$.

share|improve this answer
    
Thank you professor Clark for your clear answer. –  James Nov 2 '10 at 21:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.