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'm looking for solutions to an equation of form $m =\sqrt{x^2 - Dy^2}$. I know that $m$ is a positive integer and so the inside of the square root has to be complete square. So I'm stuck with this diophantine equation $x^2 - Dy^2 = m^2$. In the case where $m = \pm1$ that's Pell Equation which I know how to find solutions to. I also know that I can find infinitely many solutions because solutions to $x^2 - Dy^2 = 1$ are also solutions to $(mx)^2 - D(my)^2 = m^2$ but that doesn't capture all solutions.

This site seems to derive the solutions by solving $s^2 - D = 0$ mod $m^2$ but I don't know why and I don't know what to do with it. Edit: In the methods section, the hyperbolic case the author describes what seems to be this case, but I'm having a hard time following his steps. Edit2: In fact, he makes the substitution $x = sy - m^2z$ and arrives at $\frac{s^2-D}{m^2}y^2 + (2z)y + (m^2z^2) = 1$ (hence the desire to find $s = D$ mod $m^2$). Fhen he jumps to the claim that a continuous fraction expansion of roots for $\frac{s^2 - D}{m^2}t + (2s)t + m^2 = 0$ will give answers to $z$ and $y$. I guess I'm having a brain-fart on why that might be.

Most papers I find on the topic say they have a solution if $\sqrt{D} > m^2$ but that's not sufficient here.

For example: $m = 7, D = 8$ -> $x^2 - 8y^2 = 49$ and I want to be able to arrive at $x = 11; y = 3$ and other solutions where $x$ and $y$ aren't $0$ mod $7$.

Any help is appreciated. Thank you.

share|improve this question
1  
Do you know the special case $m=1$? –  vesszabo Nov 16 '12 at 10:15
1  
You can get a step-by-step solution of $x^2-8y^2=49$ (or any other 2-variable quadratic Diophantine equation) at alpertron.com.ar/QUAD.HTM –  Gerry Myerson Nov 16 '12 at 11:21
    
@vessezabo Yes. of course. did you read my question? –  McTrafik Nov 16 '12 at 23:53
    
@Gerry nice to see trying to help. In fact the link to "This site" in my post is the same link you specified. I've been trying to follow the steps in there. It gives the right solution, but I don't get where it comes from. General methods for that page is quite a read. Still getting through it. Could use a clarifcation –  McTrafik Nov 16 '12 at 23:55
    
@Will (A) - there's a particular problem I'm trying to solve where D is 8. (B) - I have a feeling m is prime otherwise x and y can be multiples of one of its prime factors. (C) Number theory - no. My background is in Bayesian stats so anything discrete is a bit outside my comfort zone, but I'm trying to learn. –  McTrafik Nov 17 '12 at 0:00

3 Answers 3

up vote 5 down vote accepted

The main book you want is Binary Quadratic Forms: Classical Theory and Modern Computations by Duncan A. Buell. He does not actually quote Lagrange's theorem on bounds, for that Introduction to the Theory of Numbers by Leonard E. Dickson. On page 111 of Dickson, we have Theorem 85 due to Lagrange, any primitively represented value $n$ occurs as the first coefficient of a reduced form in the cycle as long as $|n| < \frac{1}{2} \sqrt \Delta.$

From your edit after Gerry's last suggestion, it seems you may expect to figure this out without looking at any books. Although I give a complete algorithm below, you still will need to do some reading.

Please see my Numbers representable as $x^2 + 2y^2$ , I do not wish to retype everything.

Note: to actually find $\sqrt 8 \pmod p,$ see TONELLI or that other one
CIPOLLA. Or Berlekamp's factoring modulo primes, applied to $w^2 - 8.$

Other note: for an odd prime $q$ such that $(8|q)= -1,$ then whenever $x^2 - 8 y^2 \equiv 0 \pmod q,$ it follows that $x,y \equiv 0 \pmod q,$ so $x^2 - 8 y^2 \equiv 0 \pmod {q^2},$ and $(x/q)^2 - 8 (y/q)^2 $ is a smaller integer (in absolute value anyway).

Every odd prime $p$ such that $(8|p )= 1$ can be represented by either $x^2 - 8 y^2$ or $8 x^2 - y^2.$ These are in distinct genera.

If $p \equiv 1 \pmod 8, $ we can solve $w^2 \equiv 8 \pmod p$ and $p t - w^2 = -8.$ The indefinite quadratic form $\langle p, 2 w, t \rangle$ can be reduced to $x^2 - 8 y^2$ by a matrix in $SL_2 \mathbb Z.$ The inverse of that matrix tells us how to write one solution to $\delta^2 - 8 \gamma^2 = p.$ Then $$ (\delta^2 + 8 \gamma^2)^2 - 8 (2 \delta \gamma)^2 = p^2. $$

If $p \equiv 7 \pmod 8, $ we can solve $w^2 \equiv 8 \pmod p$ and $p t - w^2 = -8.$ The indefinite quadratic form $\langle p, 2 w, t \rangle$ can be reduced to $8x^2 - y^2$ by a matrix in $SL_2 \mathbb Z.$ The inverese of that matirx tells us how to write one solution to $8 \delta^2 - \gamma^2 = p,$ or $ \gamma^2 - 8 \delta^2 = -p.$ Then $$ (\gamma^2 + 8 \delta^2)^2 - 8 (2 \delta \gamma)^2 = (-p)^2 = p^2. $$

Given any solution $x^2 - 8 y^2 = q, $ we get a new solution by negating either $x$ or $y.$ Other then that, infinitely many new solutions are created by multiplying by the automorph as in $$ \left( \begin{array}{cc} 3 & 8 \\ 1 & 3 \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right). $$ Written as a horizontal formula $$ (3 x + 8 y)^2 - 8 (x + 3 y)^2 = x^2 - 8 y^2. $$ You can then multiply by the automorph again and again. Note that, because there is no $xy$ term, we can be satisfied with negating entries as we like and do not need to introduce the inverse of the automorph, but it does no harm if you also use it.

I will need to think a bit about completeness for this process. But experiment with it for a while, see what you can do.

POSTSCRIPT: Note that $\langle 1,0,-8 \rangle$ is not actually reduced in the sense of Gauss et al. However, it is one simple step away from $\langle 1,4,-4 \rangle,$ which is reduced.

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

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2 
1  0 -8

  0  form              1           0          -8  delta      0
  1  form             -8           0           1  delta      2
  2  form              1           4          -4


          -1          -2
           0          -1

To Return  
          -1           2
           0          -1

0  form   1 4 -4   delta  -1
1  form   -4 4 1   delta  4
2  form   1 4 -4
minimum was   1rep 1 0 disc   32 dSqrt 5.6568542495  M_Ratio  32
Automorph, written on right of Gram matrix:  
-1  -4
-1  -5
 Trace:  -6   gcd(a21, a22 - a11, a12) : 1
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 

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

share|improve this answer
JUST REPRESENTING THE PRIME ITSELF, by the first "reduced" form,
listed as 0  form. Take the left column of the matrix To Return

1  MOD  8

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
    jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2 
17 10 1

  0  form             17          10           1  delta      7
  1  form              1           4          -4


           0          -1
           1           7

To Return  
           7           1
          -1           0

0  form   1 4 -4   delta  -1
1  form   -4 4 1   delta  4
2  form   1 4 -4
minimum was   1rep 1 0 disc   32 dSqrt 5.6568542495  M_Ratio  32
Automorph, written on right of Gram matrix:  
-1  -4
-1  -5
 Trace:  -6   gcd(a21, a22 - a11, a12) : 1
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$  


jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
    jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2 
41  14  1

  0  form             41          14           1  delta      9
  1  form              1           4          -4


           0          -1
           1           9

To Return  
           9           1
          -1           0

0  form   1 4 -4   delta  -1
1  form   -4 4 1   delta  4
2  form   1 4 -4
minimum was   1rep 1 0 disc   32 dSqrt 5.6568542495  M_Ratio  32
Automorph, written on right of Gram matrix:  
-1  -4
-1  -5
 Trace:  -6   gcd(a21, a22 - a11, a12) : 1
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
    jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2 
73  18  1

  0  form             73          18           1  delta     11
  1  form              1           4          -4


           0          -1
           1          11

To Return  
          11           1
          -1           0

0  form   1 4 -4   delta  -1
1  form   -4 4 1   delta  4
2  form   1 4 -4
minimum was   1rep 1 0 disc   32 dSqrt 5.6568542495  M_Ratio  32
Automorph, written on right of Gram matrix:  
-1  -4
-1  -5
 Trace:  -6   gcd(a21, a22 - a11, a12) : 1
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
    jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2 
  89   78   17

  0  form             89          78          17  delta      2
  1  form             17         -10           1  delta     -3
  2  form              1           4          -4


          -1           3
           2          -7

To Return  
          -7          -3
          -2          -1

0  form   1 4 -4   delta  -1
1  form   -4 4 1   delta  4
2  form   1 4 -4
minimum was   1rep 1 0 disc   32 dSqrt 5.6568542495  M_Ratio  32
Automorph, written on right of Gram matrix:  
-1  -4
-1  -5
 Trace:  -6   gcd(a21, a22 - a11, a12) : 1
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$  


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

7  MOD  8

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
    jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2 
7  12  4

  0  form              7          12           4  delta      2
  1  form              4           4          -1


           0          -1
           1           2

To Return  
           2           1
          -1           0

0  form   4 4 -1   delta  -4
1  form   -1 4 4   delta  1
2  form   4 4 -1
minimum was   1rep 0 1 disc   32 dSqrt 5.6568542495  M_Ratio  2
Automorph, written on right of Gram matrix:  
-1  -1
-4  -5
 Trace:  -6   gcd(a21, a22 - a11, a12) : 1
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
    jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2 
23  20  4

  0  form             23          20           4  delta      3
  1  form              4           4          -1


           0          -1
           1           3

To Return  
           3           1
          -1           0

0  form   4 4 -1   delta  -4
1  form   -1 4 4   delta  1
2  form   4 4 -1
minimum was   1rep 0 1 disc   32 dSqrt 5.6568542495  M_Ratio  2
Automorph, written on right of Gram matrix:  
-1  -1
-4  -5
 Trace:  -6   gcd(a21, a22 - a11, a12) : 1
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
    jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2 
31  30  7

  0  form             31          30           7  delta      2
  1  form              7          -2          -1  delta     -1
  2  form             -1           4           4


          -1           1
           2          -3

To Return  
          -3          -1
          -2          -1

0  form   -1 4 4   delta  1
1  form   4 4 -1   delta  -4
2  form   -1 4 4
minimum was   1rep 1 0 disc   32 dSqrt 5.6568542495  M_Ratio  32
Automorph, written on right of Gram matrix:  
-1  4
1  -5
 Trace:  -6   gcd(a21, a22 - a11, a12) : 1
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
    jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2 
47  28  4

  0  form             47          28           4  delta      4
  1  form              4           4          -1


           0          -1
           1           4

To Return  
           4           1
          -1           0

0  form   4 4 -1   delta  -4
1  form   -1 4 4   delta  1
2  form   4 4 -1
minimum was   1rep 0 1 disc   32 dSqrt 5.6568542495  M_Ratio  2
Automorph, written on right of Gram matrix:  
-1  -1
-4  -5
 Trace:  -6   gcd(a21, a22 - a11, a12) : 1
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
    jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$
share|improve this answer

Various guises, $$ s^2 + 4 s t + 4 t^2 = (s + 2t)^2 - 8 t^2, $$ $$ -u^2 + 4 u v + 4 v^2 = 8 v^2 - (u - 2v)^2, $$ and so on as needed.

share|improve this answer

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.