# Integers of the form $x^2-ny^2$

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

• 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.
– lhf
Oct 17, 2013 at 18:10
• @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$$ Oct 17, 2013 at 18:37
• 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. Oct 17, 2013 at 18:50

## 3 Answers

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

• @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? Oct 17, 2013 at 7:50
• @SushmaPalimar I put a separate answer for $x^2 - 2 y^2.$ Oct 17, 2013 at 17:52

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. •$@WillJagy$it has been a great help from your side to explain the problem elaborately. Thank you very much for the all the help. Oct 21, 2013 at 5:38 •$@WillJagy$, Thank you very much, now I am able to do the calculations properly. Oct 21, 2013 at 11:30$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.$$ • @WillJaggy, thank you very much for your description and answer. Thanks. Oct 18, 2013 at 8:00 •$@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 Oct 22, 2013 at 14:08 • @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. Oct 22, 2013 at 17:50 • Will jagy does the same algorithm holds for integers other than prime numbers Aug 9, 2014 at 16:59 • @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. Aug 9, 2014 at 17:06