3
$\begingroup$

Here's the problem.

Find the solutions of the following equation:

$$ k^2 - 1 = 5(m^2 - 1).$$

Here's my idea:

The original equation can be written as:

$$ k^2 = 5m^2 - 4 \Longleftrightarrow k^2 - 5m^2 = -4$$

I know this is Quadratic Diophantine Equation and i've done some searching on the internet and I couldn't find a particular way for solving equations of this type. Also I know that this is a varition of Pell's equation, because instead of 1 we have -4.

I actually found the fundamental solution to this equation (by guessing) and it's (1,1). Then using this algorithm (that works for Pell's equation) I tried to generate another solution and I get:

$$ X_k+_1 = aX_k + nbY_k$$ $$ X_2 = aX_1 + nbY_1$$ $$ X_2 = 1 \times 1 + 5 \times 1 \times 1 = 6$$

$$ Y_k+_1 = bX_k + aY_k$$ $$ Y_2 = bX_1 + aY_1$$ $$ Y_2 = 1 \times 1 + 1 \times 1 = 2$$

We can easily check that (6,2) isn't a solution.

So how can I transform a Quadratic Diophantine Equation into a Pell's equatuon and how can I generate more solution for Pell's equation if the constant isn't 1 (in this case it's -4)?

Improve this question
$\endgroup$
  • $\begingroup$ Indeed, you have $6^2 - 5 \cdot 2^2 = (-4)^2 \ne -4$, which is why that algorithm doesn't work in this case $\endgroup$ – Cocopuffs Mar 24 '13 at 23:09
3
$\begingroup$

$$ A = \left( \begin{array}{cc} 9 & 20 \\ 4 & 9 \end{array} \right) , $$ and $$ A^{-1} = \left( \begin{array}{cc} 9 & -20 \\ -4 & 9 \end{array} \right). $$

$$ \left( \begin{array}{cc} 9 & 20 \\ 4 & 9 \end{array} \right) \left( \begin{array}{c} 1 \\ 1 \end{array} \right) = \left( \begin{array}{c} 29 \\ 13 \end{array} \right), $$

$$ \left( \begin{array}{cc} 9 & 20 \\ 4 & 9 \end{array} \right) \left( \begin{array}{c} 29 \\ 13 \end{array} \right) = \left( \begin{array}{c} 521 \\ 233 \end{array} \right), $$

$$ \left( \begin{array}{cc} 9 & 20 \\ 4 & 9 \end{array} \right) \left( \begin{array}{c} 521 \\ 233 \end{array} \right) = \left( \begin{array}{c} 9349 \\ 4181 \end{array} \right), $$

Switching to $-A^{-1},$ we get $$ \left( \begin{array}{cc} -9 & 20 \\ 4 & -9 \end{array} \right) \left( \begin{array}{c} 1 \\ 1 \end{array} \right) = \left( \begin{array}{c} 11 \\ -5 \end{array} \right), $$

$$ \left( \begin{array}{cc} -9 & 20 \\ 4 & -9 \end{array} \right) \left( \begin{array}{c} 11 \\ -5 \end{array} \right) = \left( \begin{array}{c} -199 \\ 89 \end{array} \right), $$

$$ \left( \begin{array}{cc} -9 & 20 \\ 4 & -9 \end{array} \right) \left( \begin{array}{c} -199 \\ 89 \end{array} \right) = \left( \begin{array}{c} 3571 \\ -1597 \end{array} \right), $$

If you want to allow common factors, $$ \left( \begin{array}{cc} 9 & 20 \\ 4 & 9 \end{array} \right) \left( \begin{array}{c} 4 \\ 2 \end{array} \right) = \left( \begin{array}{c} 76 \\ 34 \end{array} \right), $$

$$ \left( \begin{array}{cc} 9 & 20 \\ 4 & 9 \end{array} \right) \left( \begin{array}{c} 76 \\ 34 \end{array} \right) = \left( \begin{array}{c} 1364 \\ 610 \end{array} \right), $$

$$ \left( \begin{array}{cc} 9 & 20 \\ 4 & 9 \end{array} \right) \left( \begin{array}{c} 1364 \\ 610 \end{array} \right) = \left( \begin{array}{c} 24476 \\ 10946 \end{array} \right). $$

Switching to $-A^{-1},$ we get $$ \left( \begin{array}{cc} -9 & 20 \\ 4 & -9 \end{array} \right) \left( \begin{array}{c} 4 \\ 2 \end{array} \right) = \left( \begin{array}{c} 4 \\ -2 \end{array} \right), $$

$$ \left( \begin{array}{cc} -9 & 20 \\ 4 & -9 \end{array} \right) \left( \begin{array}{c} 4 \\ -2 \end{array} \right) = \left( \begin{array}{c} -76 \\ 34 \end{array} \right), $$

$$ \left( \begin{array}{cc} -9 & 20 \\ 4 & -9 \end{array} \right) \left( \begin{array}{c} -76 \\ 34 \end{array} \right) = \left( \begin{array}{c} 1364 \\ -610 \end{array} \right), $$ so you see nothing new happens this time.

Improve this answer
$\endgroup$
  • $\begingroup$ How did get A ? $\endgroup$ – Stefan4024 Mar 25 '13 at 1:28
  • 2
    $\begingroup$ @Stefan4024, the discriminant of the quadratic form $x^2 - 5 y^2$ is $20,$ and the first nontrivial solution of $u^2 - 20 v^2 = 4$ is $u=18, v = 4.$ Then, given the coefficients $ \langle \alpha, \beta, \gamma \rangle = \langle 1,0,-5 \rangle$ the simplest automorph is $$ A = \left( \begin{array}{cc} \frac{u - \beta v}{2} & - \gamma v \\ \alpha v & \frac{u + \beta v}{2} \end{array} \right) . $$ For larger discriminants it may not be this simple, perhaps more than one generator may be required. $\endgroup$ – Will Jagy Mar 25 '13 at 2:01
  • $\begingroup$ Good work. I'm still experiencing some problems with finding nontrivial solution to the original equation and the equation with discriminant. And one more question. When I write equation with discriminant, the constant (in your case 4) is negative of the constant of first equation (in this case -4). Am I right? $\endgroup$ – Stefan4024 Mar 25 '13 at 10:53
  • 1
    $\begingroup$ @Stefan4024 see this example about automorphs: math.stackexchange.com/questions/98629/… and Buell's book $\endgroup$ – Will Jagy Mar 25 '13 at 19:11
4
$\begingroup$

Here is the version from J. H. Conway's book, The Sensual Quadratic Form. What I do is add in the value of the quadratic form at the point in question, here in a color that is supposedly called fuchsia, then draw, as a column vector in green, the point in question. The main theorem is pages 20-23 of the book, the river is periodic. With my extra labelling, you can also see the automorph matrix $A$ at the second occurence of the form $\langle 1,0,-5 \rangle,$ as this $1$ happens at the column vector with entries $(9,4),$ then the $-5$ occurs at the column vector with entries $(20,9).$

Let's see, this is quite visual. It is probably most reasonable to say that the primitive representations of $-4$ have two representatives in each period, here given by $(1,1)$ and then $(11,5).$ In comparison, the representations of $-1$ happen only once per period, $(2,1),$ so the imprimitive representations of $-4$ come from $(4,2).$ For both primitive and imprimitive, all representations then occur using the automorph to jump from one period to the next.

Lagrange's "reduced" forms occur exactly where the value crosses the river, The value in yellow and the little arrow tell you what the equivalent form is: the reduced ones are, only, $\langle 1,4,-1 \rangle,$ and $\langle -1,4,1 \rangle.$ What this says is that the value $-4$ would not be found by continued fractions for $\sqrt 5.$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

enter image description here

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Improve this answer
$\endgroup$
  • $\begingroup$ I actually doesn't understand this well. I think that the opposide side of the lines are $\langle α,β,γ \rangle,$ and the automorph is the green numbers so for $\langle 1,0,-5 \rangle,$ we have: $$ A = \left( \begin{array}{cc} 9 & 20 \\ 4 & 9 \end{array} \right) , $$ and $$ A = \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right) , $$ $\endgroup$ – Stefan4024 Mar 26 '13 at 11:47
  • $\begingroup$ But whta those numbers in orange color mean? you have 6 and 10 in vertical lines and 0, 2 and 4 in horizontal. How did you get them and what those mean? And one more question how did you get those numbers in green? $\endgroup$ – Stefan4024 Mar 26 '13 at 11:49
  • $\begingroup$ I've found solution to my equation and it says that for $x^2 - 5y^2 = -4$ solutions are given by: $$\frac{x_n \pm y_n\sqrt{5}}{2} = (\frac{1\pm \sqrt{5}}{2})^n \ \text{for n = 2m-1, for any m in N}$$ How can I get generalized formula for every other quadratic Diphantine Equation. $\endgroup$ – Stefan4024 Mar 26 '13 at 12:07
  • $\begingroup$ @Stefan4024, I gave a link to a pdf for Conway's book. You will need to read the first chapter only. I drew this myself, then scanned it as a color jpeg, then posted to the site from my home computer. Buell's book is also very good; it is a reference here: en.wikipedia.org/wiki/Binary_quadratic_form and linked here books.google.com/… $\endgroup$ – Will Jagy Mar 26 '13 at 18:28
  • $\begingroup$ I can't understand this. Maybe it's because my lack of knowledge in English or it's maybe too complex for me, I don't know. I think it'll be better to show how you generate you example in the picture and explain it. Maybe it'll be clearer to me. $\endgroup$ – Stefan4024 Mar 26 '13 at 22:50
2
$\begingroup$

Hint: Consider $\left(1+\sqrt{5}\right)\left(\frac{3+\sqrt{5}}{2}\right)^n$.

Improve this answer
$\endgroup$
  • $\begingroup$ What does this means>? $\endgroup$ – Stefan4024 Mar 26 '13 at 12:36
  • 1
    $\begingroup$ It means that to get solutions, you expand as $a_n+b_n\sqrt{5}$, and the solutions of the Pell equation are $(a_n.b_n)$. And by using $a_{n+1}+b_{n+1}\sqrt{5}=(a_n+b_n\sqrt{5})\left(\frac{1+\sqrt{5}}{2} \right)$ you get the recurrence. $\endgroup$ – André Nicolas Mar 26 '13 at 15:15
  • $\begingroup$ I get it. For every n in N i get solution where the rational number is $a_n$ and the rational part of the irational number is $b_n$, am I right?. And why you have 1 in the comment instead of 3 in the answer in $(\frac{1+ \sqrt(5)}{2})$? As I understant you have to find the fundamental solution in this case (1,1). But any way to find the fundamental solution? $\endgroup$ – Stefan4024 Mar 26 '13 at 16:35
  • 1
    $\begingroup$ The $1$ in the comment is a typo, it is supposed to be $3$. Note that despite appearances the $a_n$, $b_n$ you get are magically integers, the $2$ at the bottom disappears. This is standard theory of the Pellian $x^2-dy^2=1$ when $d\equiv 1\pmod{4}$. You find the fundamental solution here by inspection, in general by doing a continued fraction expansion. It takes a chapter to do the full details. Nothing really hard. $\endgroup$ – André Nicolas Mar 26 '13 at 16:43
  • $\begingroup$ Thanks mate. It really helped me. I know how to do the continued fraction expansion and how to find the fundamental solution using it. But I thought maybe there are some other easier ways $\endgroup$ – Stefan4024 Mar 26 '13 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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