8
$\begingroup$

Solve $ 3x^2 - 2y^2 =1 $ in $ \mathbb{Z}$.

How can we do it?

( All of answers gave me a great help. Thanks a lot kind stackexchangers.)

  • 0
    @sos440: For me it is slightly smoother to multiply by $2$, and rewrite as $(2y)^2-6x^2=-2$, then $w^2-6x^2=-2$. Because $|-2|\lt \sqrt{6}$, standard theory says that any solution is obtained from a convergent $\frac{r}{s}$ of the continued fraction expansion of $\sqrt{6}$. From this we can show that there is only one "class" for $-2$. Note that $w=2$, $y=1$ is a solution. So all solutions are of shape $(a,b)$ where $a+b\sqrt{6}=(2+\sqrt{6})(5+2\sqrt{6})^n$.2012-08-12

2 Answers 2

9

This is pretty much the same information as Mark Bennet. Not the entire earthly existence of Mark Bennet, just his answer. We begin with an automorph of your indefinite quadratic form. I like to call the matrix that goes on the right the automorph, so for me it is

$ A \; = \; \left( \begin{array}{rr} 5 & 4 \\ 6 & 5 \end{array} \right) $ which solves $ \left( \begin{array}{rr} 5 & 6 \\ 4 & 5 \end{array} \right) \cdot \left( \begin{array}{rr} 3 & 0 \\ 0 & -2 \end{array} \right) \cdot \left( \begin{array}{rr} 5 & 4 \\ 6 & 5 \end{array} \right) = \left( \begin{array}{rr} 3 & 0 \\ 0 & -2 \end{array} \right) $

Note that we have $ A^{-1} \; = \; \left( \begin{array}{rr} 5 & -4 \\ -6 & 5 \end{array} \right) $

We take the convention $ A^{0} \; = \; I = \; \left( \begin{array}{rr} 1 & 0 \\ 0 & 1 \end{array} \right) $

The key thing is that any power of $A,$ positive or negative or $0,$ is also an automorph, and takes a solution of your equation as a column vector to another solution. In this case, all solutions can be generated in this manner as $ A^n \cdot \left( \begin{array}{r} 1 \\ 1 \end{array} \right). $

For example,

$ \left( \begin{array}{rr} 5 & 4 \\ 6 & 5 \end{array} \right) \cdot \left( \begin{array}{r} 1 \\ 1 \end{array} \right) = \left( \begin{array}{r} 9 \\ 11 \end{array} \right), $

$ \left( \begin{array}{rr} 5 & 4 \\ 6 & 5 \end{array} \right) \cdot \left( \begin{array}{r} 9 \\ 11 \end{array} \right) = \left( \begin{array}{r} 89 \\ 109 \end{array} \right), $ meanwhile $ \left( \begin{array}{rr} 5 & -4 \\ -6 & 5 \end{array} \right) \cdot \left( \begin{array}{r} 1 \\ 1 \end{array} \right) = \left( \begin{array}{r} 1 \\ -1 \end{array} \right), $

$ \left( \begin{array}{rr} 5 & -4 \\ -6 & 5 \end{array} \right) \cdot \left( \begin{array}{r} 1 \\ -1 \end{array} \right) = \left( \begin{array}{r} 9 \\ -11 \end{array} \right). $ Furthermore, you can still negate both entries. So all solutions are $ \pm A^n \cdot \left( \begin{array}{r} 1 \\ 1 \end{array} \right) $ with $n \in \mathbb Z.$

This is from pages 21-34 of Duncan A. Buell, Binary Quadratic Forms: Classical Theory and Modern Computations. If you had an oversized target or other difficulty, as in $3 x^2 - 2 y^2 = 25,$ the automorph idea would still work, but more "seed" vectors would be required. This is discussed in John H. Conway, The Sensual Quadratic Form.

I give an example of Conway's "river" method, including the necessary diagram, at Another quadratic Diophantine equation: How do I proceed?

I recently purchased a home scanner, it does just one page at a time but fairly well. Here, with any luck, is Conway's "River" diagram for this problem: enter image description here

Good, it is there and clear. Note how the ways to express $1$ stay close to the river, and there is just one way per cycle. I have written in the $x,y$ values for each $3x^2 - 2 y^2 = n$ as a column vector in that position. In comparison, if I wanted $3x^2 - 2y^2 = 25,$ i would have several solutions per cycle, for two reasons: for any solution of $3x^2 - 2y^2 = 1,$ I could just multiply through by $5,$ giving one imprimitive solution per cycle. There are also two primitive solutions per cycle, beginning with the two $3 \cdot 3^2 - 2 \cdot 1^2 = 3 \cdot 11^2 - 2 \cdot 13^2 = 25.$

In case it was not clear, the business with automorphs works along with the river construction, all that is really needed is correct identification of the solutions in a single cycle. So, all solutions to $3x^2 - 2 y^2 = 25$ are $ \pm A^n \cdot \left( \begin{array}{r} 5 \\ 5 \end{array} \right), \; \; \; \pm A^n \cdot \left( \begin{array}{r} 3 \\ 1 \end{array} \right), \; \; \; \pm A^n \cdot \left( \begin{array}{r} 11 \\ 13 \end{array} \right), $ with $n \in \mathbb Z.$

In case this makes any sense, this diagram is a small section of a parametrization of $PSL_2 \mathbb Z.$ All the solutions we give have $x \geq 0.$ You get the other solutions by negating both $x,y.$ Well, pages 1-33 in Conway's book.

  • 0
    Now I can verify that the reduced forms occur when crossing the river! [In the diagram](http://i.imgur.com/HQVmVKH.jpg?1), the form $(a,h,c)$ is reduced if and only if a+h+c>0, i.e. if and only if d>0. Hm, indeed I am now able to find the reduced forms for quadratic forms, in all classes except for the $0\pm$ forms, in which case the weir prevents us from crossing the river. Unless such forms as $axy$ can be said to be reduced, I could not find a reduced form for $0\pm$ forms with a weir. Regards.2013-03-29
3

If $ 3x^2-2y^2=1$ then$(\sqrt 3 x +\sqrt 2 y)(\sqrt 3 x -\sqrt 2 y) = 1$ and for any $n$ $(\sqrt 3 x +\sqrt 2 y)^n(\sqrt 3 x -\sqrt 2 y)^n = 1$

Now we have the solution $x_1=y_1=1$ which is represented by $(\sqrt 3 +\sqrt 2 )$

$(\sqrt 3 +\sqrt 2 )^2 =5+2\sqrt6$

Now this is not of the form $(\sqrt 3 x +\sqrt 2 y)$ with $x$ and $y$ integers.

BUT if we have a number of form $(\sqrt 3 p +\sqrt 2 q)$ we can verify that $(\sqrt 3 p +\sqrt 2 q)(5+2\sqrt6) = (5p+4q)\sqrt3 + (5q+6p)\sqrt2$ which is of the correct form. This enables us to generate a new solution from an old one, because, assuming $3p^2-2q^2=1$:

$3(5p+4q)^2 - 2(5q+6p)^2 = 75p^2+120pq+48q^2-50q^2-120pq-72p^2=3p^2-2q^2=1$

This gives us a recurrence $x_n= 5x_{n-1}+4y_{n-1}\text{, } y_n=6x_{n-1}+5y_{n-1}$ which generates solutions.

We can put this in reverse too: $x_{n-1} = 5x_n-4y_n \text{ and } y_{n-1} = 5y_n-6x_n$

NOW suppose we have a solution to the original equation. We can change the sign of $x$ and $y$ if necessary, so that they are both positive. Apply the descending recurrence to find a solution with smaller $x$ - but since $x$ is a positive integer, the process has to stop, and we can see that every solution is derived by recurrence from $(x,y)=(1,1)$ and then taking account of the possible signs.

There are various apparent coincidences here which are explained in more general theory

  • 0
    André Nicholas shows in his comment how to convert to an easier standard form. If you look at the Pell Equation and Continued Fractions you'll find general theory. Using a recurrence "backwards" to find a smaller solution is a little trick I haven't often seen described (there are some details to complete in that bit).2012-08-12