9
$\begingroup$

Is there any algorithm to represent the given integers in the form $N=x^2-ny^2$, $n>1$, say for $n=2$. As we have for any prime, $p$, a prime $q$ can be written as $q=x^2+py^2$,whenever $q$ is a quadratic residue of $p$ called cornacchia algorithm

$\endgroup$
3
  • $\begingroup$ An important reference is the book Primes of the Form $x^2+ny^2$, by David Cox, but I'm not sure it discusses algorithms. $\endgroup$
    – lhf
    Oct 17, 2013 at 18:10
  • 1
    $\begingroup$ @lhf, I give the only necessary general algorithm in a separate answer for $x^2 - 2 y^2.$ This should also suffice for $x^2 - r y^2$ when $r \equiv 5 \pmod 8$ is prime and the class number is one (so NOT $x^2 - 37 y^2$) and the beginnings of a method for $x^2 - s y^2$ when $s \equiv 1 \pmod 8$ is prime and the class number is one; although it is probably going to be more satisfactory to consider $$ x^2 + x y - \frac{s-1}{4} y^2 $$ $\endgroup$
    – Will Jagy
    Oct 17, 2013 at 18:37
  • 1
    $\begingroup$ Oh, if we have prime $r \equiv 1 \pmod 4,$ there is always a solution to $x^2 - r y^2 = -1,$ which greatly simplifies matters. This is proved in Mordell's book. Also, while $x^2 - 37 y^2$ behaves badly, $x^2 + x y - 9 y^2$ has class number one and everything works well. $\endgroup$
    – Will Jagy
    Oct 17, 2013 at 18:50

3 Answers 3

7
$\begingroup$

Things are not as simple as you seem to think, even for positive forms. Among primes with $ (p|23) = 1,$ approximately $1/3$ are integrally represented by $x^2 + 23 y^2.$ Below are all the primes in question, up to 1000. Among primes $p \neq 2,3,23,$ with $ (p|23) = 1,$ the ones with $p = x^2 + 23 y^2 $ are those for which $x^3 - x + 1$ has three distinct roots $\pmod p.$ Also note that $x^2 + 23 y^2$ and $x^2 + x y + 6 y^2$ represent exactly the same odd numbers. Then, $ 3x^2 + 2xy + 8 y^2$ and $2 x^2 + x y + 3 y^2$ represent exactly the same odd numbers. See Hudson and Williams 1991 at http://zakuski.utsa.edu/~jagy/inhom.html

    p = x^2 + 23 y^2 
           p         p % 23
----------------------------
          23           0
          59          13
         101           9
         167           6
         173          12
         211           4
         223          16
         271          18
         307           8
         317          18
         347           2
         449          12
         463           3
         593          18
         599           1
         607           9
         691           1
         719           6
         809           4
         821          16
         829           1
         853           2
         877           3
         883           9
         991           2
         997           8

    0    1    2    3    4    6    8    9   12   13   16   18 : mod 23 

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

    p = 3 x^2 + 2 x y + 8 y^2 
           p         p % 23
----------------------------
           3           3
          13          13
          29           6
          31           8
          41          18
          47           1
          71           2
          73           4
         127          12
         131          16
         139           1
         151          13
         163           2
         179          18
         193           9
         197          13
         233           3
         239           9
         257           4
         269          16
         277           1
         311          12
         331           9
         349           4
         353           8
         397           6
         409          18
         439           2
         443           6
         461           1
         487           4
         491           8
         499          16
         509           3
         541          12
         547          18
         577           2
         587          12
         601           3
         647           3
         653           9
         673           6
         683          16
         739           3
         761           2
         811           6
         823          18
         857           6
         859           8
         863          12
         887          13
         929           9
         947           4
         967           1


    1    2    3    4    6    8    9   12   13   16   18 : mod 23 
$\endgroup$
2
  • $\begingroup$ @WillJaggy Thank you, yes for $n=1,2,3,4,7$, $x^+ny^2$ is well said, in terms of Legendre symbol, depends on the number of genus and each genera. so given an integer to represent in the form X^2-2y^2 could be difficult is it so? $\endgroup$
    – Math123
    Oct 17, 2013 at 7:50
  • 1
    $\begingroup$ @SushmaPalimar I put a separate answer for $x^2 - 2 y^2.$ $\endgroup$
    – Will Jagy
    Oct 17, 2013 at 17:52
4
$\begingroup$

Example, prime $p= 159287$

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 
159287  113296  20146

  0  form         159287      113296       20146  delta      2
  1  form          20146      -32712       13279  delta     -2
  2  form          13279      -20404        7838  delta     -2
  3  form           7838      -10948        3823  delta     -2
  4  form           3823       -4344        1234  delta     -2
  5  form           1234        -592          71  delta     -5
  6  form             71        -118          49  delta     -2
  7  form             49         -78          31  delta     -2
  8  form             31         -46          17  delta     -2
  9  form             17         -22           7  delta     -2
 10  form              7          -6           1  delta     -2
 11  form              1           2          -1


          85        -101
        -239         284

To Return  
         284         101
         239          85

0  form   1 2 -1   delta  -2
1  form   -1 2 1   delta  2
2  form   1 2 -1

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

The discriminant is $D=8.$ A form $\langle a,b,c \rangle$ is reduced if $0 < b < \sqrt D$ AND $\sqrt D - b < 2 |a| < \sqrt D + b.$

THEOREM. The following are equivalent, when $D$ is positive and not a square, and of course $D = b^2 - 4 a c$:

(I) $0 < b < \sqrt D$ AND $\sqrt D - b < 2 |a| < \sqrt D + b.$

(II) $0 < b < \sqrt D$ AND $\sqrt D - b < 2 |c| < \sqrt D + b.$

(III) $ac < 0$ AND $b > |a+c|.$

If a form is not reduced (by any of the three tests above (I), (II), (III), we can reduce it, one step at a time, by finding the (unique) integral $\delta$ such that $$ \sqrt D - 2 |c| < -b + 2 c \delta < \sqrt D. $$ The next form is then $$\langle c, -b + 2 c \delta, a - b \delta + c \delta^2 \rangle$$ The change of variables matrix that accomplishes this on the level of Gram matrices is $$ \left( \begin{array}{cc} 0 & -1 \\ 1 & \delta \end{array}\right) $$

In the example, we get from the original $\langle 159287, 113296, 20146 \rangle$ to the reduced $\langle 1, 2, -1 \rangle$ by means of the matrix $$ \left( \begin{array}{cc} 85 & -101 \\ -239 & 284 \end{array}\right) $$ To get from $\langle 1, 2, -1 \rangle$ to (non-reduced) $\langle 1, 0, -2 \rangle$ we use $$ \left( \begin{array}{cc} 1 & -1 \\ 0 & 1 \end{array}\right) $$ to arrive at $$ \left( \begin{array}{cc} 85 & -186 \\ -239 & 523 \end{array}\right). $$

Inverse $$ \left( \begin{array}{cc} 523 & 186 \\ 239 & 85 \end{array}\right). $$

So, $$ \left( \begin{array}{cc} 523 & 239 \\ 186 & 85 \end{array}\right) \left( \begin{array}{cc} 1 & 0 \\ 0 & -2 \end{array}\right) \left( \begin{array}{cc} 523 & 186 \\ 239 & 85 \end{array}\right) = \left( \begin{array}{cc} 159287 & 56648 \\ 56648 & 20146 \end{array}\right) $$

So $$ 523^2 - 2 \cdot 239^2 = 159287. $$

NOTE: if $n>0 $ is not a square, and $s_0 = \lfloor \sqrt n \rfloor,$ then $\langle 1, 0, -n \rangle$ is not reduced but $\langle 1, 2 s_0, s_0^2 - n \rangle$ is reduced. The quickest transformation is just $$ \left( \begin{array}{cc} 1 & s_0 \\ 0 & 1 \end{array}\right) $$

Three books with part or all of this are : (1929) Introduction to the Theory of Numbers, by Leonard Eugene Dickson; (1989) Binary Quadratic Forms, by Duncan A. Buell; (2007) Binary Quadratic Forms, by Johannes Buchmann and Ulrich Vollmer.

$\endgroup$
2
  • $\begingroup$ $@WillJagy$ it has been a great help from your side to explain the problem elaborately. Thank you very much for the all the help. $\endgroup$
    – Math123
    Oct 21, 2013 at 5:38
  • $\begingroup$ $@WillJagy$, Thank you very much, now I am able to do the calculations properly. $\endgroup$
    – Math123
    Oct 21, 2013 at 11:30
3
$\begingroup$

$x^2 - 2 y^2$ is quite easy. Both $2$ and $-1$ are represented. Next, if we have a (positive) prime $p \equiv \pm 1 \pmod 8,$ we know $(8|p) = 1.$ So, solve $$ b^2 \equiv 8 \pmod {4 p}. $$ This is just solving $$ \beta^2 \equiv 8 \pmod p, $$ using TONELLI SHANKS or CIPOLLA, then choosing $p - \beta$ if $\beta$ is odd. So, now we have $$ b^2 - 4 p c = 8 $$ for some integer $c.$ That is, we have an indefinite binary form $$ \langle p,b,c \rangle $$ of discriminant 8. It reduces, by some $P \in SL_2 \mathbb Z,$ to $ \langle 1,0,-2 \rangle. $ So $P^{-1}$ does the reverse process, and the left hand column of $P^{-1}$ shows how to write $p = x^2 - 2 y^2.$ I like the description of reduction for indefinite forms in Duncan A. Buell, Binary Quadratic Forms, that is what I use, but some version is in many books.

Finally, for multiplication, $$ (u^2 - 2 v^2)(x^2 - 2 y^2) = (ux-2vy)^2 - 2 (uy-vx)^2. $$

$\endgroup$
6
  • $\begingroup$ @WillJaggy, thank you very much for your description and answer. Thanks. $\endgroup$
    – Math123
    Oct 18, 2013 at 8:00
  • $\begingroup$ $@WillJagy$I wrote python code to generate $<1,2,-1>$ from $<p,b,c>$. Answer comes properly for some small numbers of size 7 digits. But if the digits are more say for $p=9444732965601851473921$, evaluating $b$ or $\beta$ such that $\beta^2\equiv 8 \pmod{p}$ was not possible. I gave the range for $\beta$ in [1,(p+1)/2, 1]; is the range wrong or is it computationally not feasible? Thanks $\endgroup$
    – Math123
    Oct 22, 2013 at 14:08
  • $\begingroup$ @SushmaPalimar, I don't know python. I use C++ with GMP; as a result, if I have large numbers and a correct method, and I have correctly converted everything to integer arithmetic, it all works out. I have never felt the need to implement Cipolla or Tonelli-Shanks; you will need to read up on these. $\endgroup$
    – Will Jagy
    Oct 22, 2013 at 17:50
  • $\begingroup$ Will jagy does the same algorithm holds for integers other than prime numbers $\endgroup$
    – Math123
    Aug 9, 2014 at 16:59
  • $\begingroup$ @Sushma, I suppose. If you just need one representation you can do this for each prime divisor that is $\pm 1 \bmod 8$ and use the multiplication rule I gave. $\endgroup$
    – Will Jagy
    Aug 9, 2014 at 17:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .