Ordering the solutions to Pell's Equation

Question

Let $S$ be the set of positive integer pairs $(x,y)$ such that $x^2 - d y^2 = -4$ or $x^2 - d y^2 = 4$, where $d$ is fixed as the discriminant of a real quadratic number field.

I'm trying to show that if $(x, y) \in S$ and $(a,b) \in S$ with $x \lt a$, then $y \lt b$. (or find a counterexample)

Graphing $x^2$ as a function of $y^2$ you can see that the points in $S$ lie on two possible parallel lines with slope $d$. It's conceivable then that a point may lie "above and to the left" of another point, which would disprove my conjecture.

Answer 1

Suppose we have two solutions $(a,b)$ and $(x,y)$ with $a\gt x$ and $y\gt b$. We note that we can choose $x,y,a,b \ge 0$ just by changing the sign.

Then $a^2\gt x^2$ so that $\pm 4+db^2\gt \pm 4+dy^2$ or $\pm 4\mp 4\gt d(y^2-b^2)=d(y-b)(y+b)\gt 0$ (since $y-b\gt 0$)

Hence we have $$8\gt d(y-b)(y+b)\gt 0$$ and the choice of signs is $+$ for $(a,b)$ and $-$ for $(x,y)$

... a product of three integers with $y\gt b$. This constraint alone reduces the possibilities to

$(d,y,b)=(1,1,0);(1,2,0); (1,2,1); (1,3,2);(1,4,3); (2,1,0); (2,2,1); (3,1,0); (4,1,0);(5,1,0);(6,1,0);(7,1,0)$

Many of these have $b=0$ when $a^2=4, a=2$. Then $a\gt x$ means $x=0$ or $x=1$ giving the possibilities $dy^2=4$ or $dy^2=5$

The first is possible with $d=1, y=2$ or with $d=4, y=1$, and the second works with $d=5, y=1$

So we have $$2^2-1\cdot 0^2=4; 0^2-1\cdot 2^2=-4$$ $$2^2-4\cdot 0^2=4; 0^2-4\cdot 1^2=-4$$ $$2^2-5\cdot 0^2=4; 1^2-5\cdot 1^2=-4$$

The possibilities where $d=1, b\gt0$ lead to $a^2=5, 8, 13$. The final option is $d=2, b=1$ which would give $a^2=12$. So these give no solutions.

---

What I missed is that the case $y=b$ is also allowed:

In the case with $y=b$ the product will always equal zero, but we can recast the problem as$$a^2-db^2=4; x^2-db^2=-4$$ This gives us simply $$a^2-x^2=(a+x)(a-x)=8$$ The two factors have to be of the same parity, so $a+x=4, a-x=2, a=3, x=1$. Then $9-db^2=4$ so $db^2=5, d=5, b=y=1$, which is what Burak found.

For interest, if you allow $x=a$ this means the product can be equal to $8=1\times 1\times 8=1\times 2\times 4=2\times 2\times 2$ and noting that $y-b$ and $y+b$ have the same parity, there are extra possibilities, namely:

$$(d,y,b)=(8,1,0); (1,3,1); (2,2,0)$$

The first of these has $b=0$, and the analysis of that case shows there is no new solution. The second with $y=3, d=1$ gives $x^2-1\cdot 3^2=-4$ or $x^2=5$. The final case gives $x^2-2\cdot 2^2=-4$, whence $x=2$. And then $a^2-2\cdot 2^2=4$ or $a^2=12$. So the $x=a$ case leads to no extra solution.

This exhausts the equality cases.

Answer 2

I set about finding a particular solution for $D$, such that $a^2-D\cdot b^2 = 4$.

When you take the set $\mathbb Q(\sqrt D)$, the set is closed to division, except by zero, so it's pretty pointless about looking for 'fundemental units'. On the other hand, one can look at a set \mathbb Z(d), where $d$ is $\sqrt D$ for $D=2, 3 \pmod 4$, or $\frac 12 \sqrt D+\frac 12$. when $D = 1 \pmod 4$.

The process is a fairly straight-forward loop, with a definite solution, plus a search for a solution elsewhere. It usually finds the smallest value for even $a$, but for some numbers it finds the pseudoroot (ie $a^2-D\cdot b^2=-4$), or it finds the isocube for odd $a$.

The following is an extract for finding a value of $A$ that works. The final value to be returned, might be variously $A^2+2$ or $A=a^3-3a$, or both tests applied. I've used the program as far as $D=1800$ without any further comment.

What follows is an ancient readme i wrote years ago, precisely to solve Pell's equation for random numbers, the value to be a minimum value of the type ye seek. "Isomprohic Roots" is my expression for the solutopn of Pell's equation.

 IsoBase

 A program to determine the isomorphic root.  This is a number whose square
 excede by four, the square of the isobase root.  Thus the isobase for 5 is
 three, since nine excedes five by four.

 It is desired to create a program, that the input is an natural number n,
 and the output is the smallest z, that z*z - n*y*y = 4, for integer z, y.
 The form of the command is 'ISOBASE 5' prints '3'.

 This can be done by continued fractions, which we expediate by killing it
 off as fast as we can.  The worked example is for base 21.

 Let base = 21; and x = sqrt(21) = 4.58257569496

 4.58257569496 = 4 + 1/1.71651513898 = 4 + ( -4 + x)        2
 1.71651513898 = 1 + 1/1.39564392376 = 1 + ( -1 + x) / 5    2
 1.39564392376 = 1 + 1/2.52752523152 = 1 + ( -3 + x) / 4    4 = 1 *  2 +  2
 2.52752523152 = 2 + 1/1.89564392421 = 2 + ( -3 + x) / 3   10 = 2 *  4 +  2
 1.89564392421 = 1 + 1/1.11651513840 = 1 + ( -1 + x) / 4   14 = 1 * 10 +  4
 1.11651513840 = 1 + 1/8.58257573850 = 1 + ( -4 + x) / 5   24 = 1 * 14 + 10
 8.58257573850 = 4 + x               = 8 + ( -4 + x)      110 = 4 * 24 + 14

Where 110 = the cube of 5, also, 110 * 110 - 24 * 24 * 1 = 4.

On paper, one sets this out thus

       a    b    c    d    e    f    g
  0         2
  1         0    0    1         1
  2    4    2    4    1    5    5
  3    1    2    1    1   20    4
  4    1    4    3    1   12    3
  5    2   10    3    1   12    4
  6    1   14    1    1   20    5
  7    1   24    4    1    5    1   *
  8    4  110

 For a prime like 113

       a   b    c    d    e    f    g
   0       2
   1       0    0    1         1
   2  10   2   10    1   13   13
   3   1   2    3    1  104    8
   4   1   4    5    1   88   11
   5   1   6    6    1   77    7
   6   2  16    8    1   49    7
   7   2  38    6    1   77   11
   8   1  54    5    1   88    8
   9   1  92    3    1  104   13
  10   1 146   10    1   13    1   *
  11  10 1552

   1552 * 1552 < 146 * 146 * 113
    4817412

 This method works on evaluating the continued fraction of x, which forms in
 the values a. The values in c, d, and f represent the fractional part of the
 next term, ie

  a + (-c + dx) / f = a; f/(-c+dx)
                    = a; (c+dx)f/e     Where e = d*d*x - c*c
 Since f/e can be reduced, (usually because f divides e)

 Some form of code for this. We operate on a window of current values. Let us
 work on row 2, for example, keeping just those variables required to move
 from row to row.  Here, a1 means the value of a in row 1.

    a0  b0  c0  d0  e0  f0
    a1  b1  c1  d1  e1  f1

    a2  b2  c2  d2  e2  f2
    b0 = 2; b1 = 0; c1 = 0; d1 = 1; f1 = 1

   a2 = (c1 + d1 * x ) % f1
   b2 = a2 * b1 + b0
   c2 = a2 * f2 - c1
   d2 = d2
   e2 = d2 * d2 * bb - c2 * c2
   f2 = e2 / f1
   if f2 \= 1 then iterate
   return b3 = b2 * c2 + b1

Answer 3

Suppose you have a point $(x,y)$ on the lower "line" (a solution to $dy^2 = x^2-4$). Now consider the region of the plane that is "upper left" from that point. The other line only visits the region very briefly : from $(x',y)$ to $(x,y')$ with $x'^2 = x^2-8$ and $dy'^2 = dy^2+8$.

This line stays very close to $(x,y)$, so it can't possibly meet another point with integer coordinates, for example if $x' > x-1$ and $y' < y+1$.

These two bounds gives you a bound on $(x,y)$ : solving the equation on $x$ gives you that if $x > \frac 92$, then $x' > x-1$, which shows that from there the only possible kind of counterexample is when $x' = x$ and $y' > y$. Solving the equation on $y$ then gives you that if $y > \frac{8-d}{2d}$ then $y' < y+1$ so there is a bounded region where counterexamples may lie.

Since $\frac{8-d}{2d} \le 8$, and for $y \le 8$, $y'^2 \le 64+8/d \le 72 < 9^2$, you only need to check counterexamples among the values $0 \le x \le 4$ and $0 \le y \le 8$

Answer 4

A counterexample would be the pairs (1, 1) , (3, 1) which are in set $ S $ since for $ d=5 $, (1, 1) satisfies $ x^2-5y^2=-4$ and (3, 1) satisfies $ x^2 -5 y^2 =4 $. You can further show that this is the only case by making use of $(n+k)^2-n^2=2 n k+k^2 $ . I hope this helps.