MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $N \ $ be a positive integer, which is a square times a product of distinct primes, each of which is either 2 or is congruent to $\pm 1$ mod 8. Then I wish to show that there are positive $K$ and $M$ with $ M < K $ such that $N = 2K^2 - M^2$. The equation is obviously related to the quadratic form $f(x,y,z) = Nx^2 +y^2 -2 z^2$. One can use the Hasse-Minkowski theorem to show that this equation always has a nontrivial rational solution.

We want integer solutions with $x=1$, $y > 0$, and $y < z$. The problem divides into two parts: show there is a solution with $x=1$, i.e. an integer solution to the original equation, and then show that there is a solution satisfying the desired bound.

Here is what I tried:

Corollary 6.3.6, p. 345 of Cohen volume 1, tells us how all rational solutions can be parametrized in terms of a given solution, which is pretty interesting, but not helpful, since you need one solution to start with.

Prop. 6.3.12 tells how to find one solution, and indeed one in which (x,y,z) are integers. The equation six lines above 6.3.12 (p. 351) and the displayed equation in the middle of that page together give a bound on the size of $x$, something like $3/2$ times the cube root of $N$. But they do not give a bound on $y$ and $z$. These would come out of the LLL algorithm used in the proof, so bounding the solution might be a matter of understanding that algorithm. But anyway, this line of reasoning doesn't address the first part of the problem, the existence of an integer solution with $x=1$.

In case someone asks why I care about this, the equation comes up in my work on tiling a triangle by congruent triangles.

share|cite|improve this question
Solutions for the squarefree case give solutions for the general problem. It may also be possible to combine solutions from relatively prime N. Do you have any results in the case N is a prime of the necessary form? Gerhard "Ask Me About System Design" Paseman, 2012.01.23 – Gerhard Paseman Jan 23 '12 at 16:30
Yes, we can assume N is square free, but I don't know how to combine solutions for different primes, nor how to solve the equation even if N is prime. I tested it by computer and empirically it does have solutions. – Michael Beeson Jan 23 '12 at 16:44
google for Brahmagupta identity. This reduces the problem to prime values of N, and for these it is a well known theorem. – Franz Lemmermeyer Jan 23 '12 at 17:11
(1) Thanks for pointing out that identity. It reduces the problem of finding an integer solution to the case $N$ prime, but it doesn't seem that the inequality $0 < y < z$ is preserved. (2) Where can I find this "well known theorem"? I don't find it in Cohen volume 1. There is a book by Cox, primes of the form $s^2 + ny^2$, but in that book $n$ is always positive. – Michael Beeson Jan 23 '12 at 17:29
If $(M,K)$ works then so does $(3M \pm 4K, 2M \pm 3K)$ [this corresponds to the fundamental positive unit $3 \pm 2 \sqrt{2}$ in ${\bf Z}(\sqrt{2})$]. Now iterate until $|M/K|$ is minimal. – Noam D. Elkies Jan 23 '12 at 17:39
up vote 2 down vote accepted

I recommend you get Binary Quadratic Forms by Duncan A. Buell.

Theorem 4.23 on page 74 is, when $p$ is an odd prime with $(\Delta | p) = 1,$ and $b$ is any integral solution to $b^2 \equiv \Delta \pmod {4p},$ the $p$ is primitively represented by the binary quadratic forms belonging to the classes of $\langle p, b, \ast \rangle$ and its opposite $\langle p, -b, \ast \rangle$

In you case, the discriminant $\Delta$ of $x^2 - 2 y^2$ is 8. There are no imprimitive forms of this discriminant, so we may ignore the word "primitively." On page 30, we find that there is only one equivalence class of forms of this discriminant. As a result, any prime $p \equiv \pm 1 \pmod 8$ is represented by $x^2 - 2 y^2.$

How to find a representation? Using TONELLI-SHANKS solve $b^2 \equiv 8 \pmod p.$ If $b$ is odd, replace it by $p-b$ to get an even value, so now $b^2 \equiv 8 \pmod {4p}.$ That is, $b^2 = 8 + 4 p t,$ Which is to say $$ b^2 - 4 pt = 8.$$ So we have an indefinite form, almost certainly not "reduced," $$\langle p, b, t \rangle.$$ Pages 21-26 in Buell tell you everything necessary about indefinite reduced forms, with some positive discriminant $D$ not a square, and some coefficients $\langle a, b, c \rangle$ with $b^2 - 4 a c = D,$ the form is reduced if $$ 0 < b < \sqrt D \; \; \mbox{and} \; \; \sqrt D - b < 2 |a| < \sqrt D + b $$ The reduced form of discriminant 8 are $\langle 1,2,-1 \rangle$ and $\langle -1,2,1 \rangle,$ these being equivalent.

Finally, on page 22, we have Proposition 3.3, any indefinite form is equivalent to a reduced form of the same discriminant. Furthermore, in the body of the proof, Buell shows exactly how to get from non-reduced $\langle p, b, t \rangle$ to one of the reduced forms mentioned, also resulting in a 2 by 2 matrix of determinant 1, let us call it $R,$ which provides the (invertible) change of variables. Inverting $R$ tels us how to get from the reduced form to $\langle p, b, t \rangle.$ A little extra care lets us find a solution to $v^2 - 2 w^2 = p.$

The fact that $x^2 - 2 y^2$ integrally represents all primes $p \equiv \pm 1 \pmod 8$ is due to people such as Lagrange (Franz would know). Lagrange would have seen this material in the way I describe, if you can find it see Introduction to the Theory of Numbers by Leonard Eugene Dickson.

I have software I wrote that takes an indefinite form and reduces it, then shows the entire "chain" or "cycle" of reduced equivalent forms. Email me if you would like a copy (it is in C++). Also, your name seems very familiar, perhaps you are Marvin Greenberg's friend who wrote to me once or twice? Not sure.

A note about speed. This all works very rapidly. It is essentially finding the repeated part of a continued fraction for a quadratic irrational. Indeed, the special thing about reduced forms is that the continued fraction for the largest root is purely periodic.

EDIT, 25 January 2012: I finally got the reduction step cleaned up with a nice printout. I find a pretty example, $p = 159287$ and $45991^2 \equiv 8 \pmod {159287}.$ Then $159287 - 45991 = 113296$ is even, and the constructed indefinite form of discriminant $D = 8$ is $$ \langle 159287, \; 113296, \; 20146 \rangle. $$ The reduction step is this: we find the (unique) integral $\delta$ such that $$ \sqrt D - 2 |c| < -b + 2 c \delta < \sqrt D. $$ Then the next form is $$ \langle c, \; -b + 2 c \delta , \; a - b \delta + c \delta^2 \rangle. $$

The change of variables matrix is just $$ \left( \begin{array}{cc} 0 & -1 \\\ 1 & \delta \end{array} \right) $$ As we follow through several steps, we just keep a running account of the matrix. At the end, we have the matrix, written on the right, that takes the original form to the resulting reduced form. The inverse takes the reduced form back. Here is the output:

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
minimum was   1rep 1 0 disc   8 dSqrt 2.8284271247  M_Ratio  8
Automorph, written on right of Gram matrix:  
-1  -2
-2  -5
 Trace:  -6   gcd(a21, a22 - a11, a12) : 2
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 

The matrix of the form $ \langle 1, \; 2, \; -1 \rangle $ is $$ \left( \begin{array}{cc} 1 & 1 \\\ 1 & -1 \end{array} \right) $$ and the part about returning is $$ \left( \begin{array}{cc} 284 & 239 \\\ 101 & 85 \end{array} \right) \cdot \left( \begin{array}{cc} 1 & 1 \\\ 1 & -1 \end{array} \right) \cdot \left( \begin{array}{cc} 284 & 101 \\\ 239 & 85 \end{array} \right) = \left( \begin{array}{cc} 159287 & 56648 \\\ 56648 & 20146 \end{array} \right), $$ which says that $$ 284^2 + 2 \cdot 284 \cdot 239 - 239^2 = 159287$$ and applying $$ \left( \begin{array}{cc} 1 & 1 \\\ 0 & 1 \end{array} \right) \cdot \left( \begin{array}{c} 284 \\\ 239 \end{array} \right) = \left( \begin{array}{c} 523 \\\ 239 \end{array} \right) $$ tells us that $$ 523^2 - 2 \cdot 239^2 = 159287. $$

share|cite|improve this answer
Right, the hardest part of this is factoring $N$. – Noam D. Elkies Jan 23 '12 at 22:45
Noam, yes, for a single prime the illustrated procedure gives you a reduced form that represents it, and reversing gives the representation. If the class number is 1 that wraps up that part of the story. It appears that Tonelli-Shanks is also fast, the only uncertain thing is finding a quadratic nonresidue, and a GRH says that is rapid as well. – Will Jagy Jan 23 '12 at 23:18
You can even get the square root of 2 modulo a prime $p$ in deterministic polynomial time using Schoof's algorithm... If $p \equiv -1 \bmod 8$ then $-1$ is a quadratic nonresidue; if $p \equiv +1 \bmod 8$, the trace of the CM elliptic curves of discriminant $-4$ and $-8$ yields square roots of $-1$ and $-2 \bmod p$, and their product is a square root of $2$. Yes you'd never do it that way in practice but it's still asymptotically faster than factoring. – Noam D. Elkies Jan 24 '12 at 0:03
Thanks, Noam, I don't believe I knew of Schoof's algorithm. I'm gradually working up the energy to write a good program for my… which amounts to: take a long string of consecutive numbers, all of which are represented by at least one positive binary form of discriminant $-q$ for my choice of prime $q \equiv 7 \pmod 8,$ for each number find all reduced forms that actually do represent it. See if the whole string is represented by a single form... Easy mathematics, long program. – Will Jagy Jan 24 '12 at 0:26

Your Answer


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.