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.

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

share|improve this question
    
Have you tried anything at all? For example, it is obvious that $\,x\,$ must be odd...or isn't it? –  DonAntonio Aug 12 '12 at 17:15
    
Yes $$x$$ must be odd...... –  Guldam Aug 12 '12 at 17:17
    
How about relating it to Pell's equation? I found that any pair of integers $(x_n, y_n)$ satisfying $$3x_n + y_n\sqrt{6} = (5+2\sqrt{6})^n (3+\sqrt{6})$$ is a solution to the given equation, and I suspect that (up to change of sign) these are the solutions. –  sos440 Aug 12 '12 at 17:18
    
Relating Pell's equation 을 어떻게 하는지 그 과정을 잘 모르겠습니다.. (It is the point that I am very wondering...) Would you give me a kind derivation, please?.. Thank you in advance. –  Guldam Aug 12 '12 at 17:26
    
I'm afraid I am bad at number theory. I know how to construct a family of solutions via fundamental solutions, but I do not know how to prove that these exhaust all the possibility. I believe someone else will give you a nice description in this way, or in a better way. –  sos440 Aug 12 '12 at 17:32

2 Answers 2

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.

share|improve this answer
    
Beautiful ... and worth knowing –  Mark Bennet Aug 12 '12 at 22:45
2  
@MarkBennet, thank you. I added in a diagram. For a very small squarefree target number such as $1$ in $3x^2 - 2 y^2 = 1$ there are no actual differences among Legendre's right neighbor method, continued fractions, and Conway's diagram. That is, $3 x^2 - 2 y^2$ and $x^2 - 6 y^2$ are integrally equivalent quadratic forms. –  Will Jagy Aug 12 '12 at 23:23
    
Now I can verify that the reduced forms occur when crossing the river! In the diagram, 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. –  awllower Mar 29 '13 at 8:54

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

share|improve this answer
    
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). –  Mark Bennet Aug 12 '12 at 19:15

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.