Solve $37x^2-113y^2=n$

Question

Prove that if these equations : $$37a^2\equiv n\pmod {113}\tag 1$$ $$-113b^2\equiv n\pmod {37}\tag 2$$ $$37c^2\equiv 113\pmod {n}\tag 3$$ have integer solutions, then the equation $$37x^2-113y^2=n$$ has integer solutions.

Answer 1

Disclaimer

This is not a complete answer to your question because it only works when $n$ is not divisible by $37$ or $113$. I think we should be able to go around this restriction without too much more work, but here is what I have so far.

Introduction

By a primitive integral binary quadratic form, I mean one whose coefficients are relatively prime.

The first thing I did was to find out the number of equivalence classes of primitive integral binary quadratic forms of discriminant $D = -4 \cdot 37 \cdot (-113) = 16724$. The reduction algorithm is not too complicated, but I used the online applet here because the discriminant is rather big. It says that there are two equivalence classes, with $x^2 + 128xy -85y^2$ and $5x^2 + 122xy - 92y^2$ serving as possible representatives.

It is important to note that the applet disregards non-primitive forms. This is relevant because $16724$ is not a fundamental discriminant. There are in fact two more equivalence classes of non-primitive forms with discriminant $16724$ --- basically primitive forms with discriminant $4181$ scaled by $2$. We will come back to this when we carry out the second part of our plan.

This means that for any given primitive integral binary quadratic form $AX^2 + BXY + CY^2$ of discriminant $16724$, we can find a matrix $M \in GL_{2}(\mathbb{Z})$ such that $$ M^{t} \begin{pmatrix} A & \frac{B}{2} \\ \frac{B}{2} & C \end{pmatrix} M = \begin{pmatrix} 1 & 64 \\ 64 & -85 \end{pmatrix} \ \ \text{or} \ \ \begin{pmatrix} 5 & 61 \\ 61 & -92 \end{pmatrix}. $$ We can also think of this as there being an integrally invertible change of variables $$ \begin{pmatrix} X \\ Y \end{pmatrix} = M \begin{pmatrix} x \\ y \end{pmatrix} $$ which will turn $AX^2 + BXY + CY^2$ into one of the two representative forms. In particular, the set of integers represented by a primitive form of discriminant $16724$ coincides with the corresponding set of one of the two representative forms.

So here is our plan to exploit the congruence conditions given in the question:

1. Find a way to distinguish numbers represented by the two representative forms.
2. Show that $n$ is represented by some primitive form of discriminant $16724$

First part of the plan

By completing the squares, we can write $$ x^2 + 128xy -85y^2 = (x + 64y)^2 - (37 \cdot 113) y^2. $$ If $n$ is represented by that form, we know from reducing modulo $37$ or $113$ that $n$ is a square modulo both primes. We can do something similar for the other form to get $$ 5x^2 + 122xy - 92y^2 = \frac{1}{5} \left\{ (5x+61y)^2 - (37 \cdot 113)y^2 \right\}. $$ So if $n$ is represented by the second form, $5n$ must be a square modulo both $37$ and $113$. If we assume that $n$ is relatively prime to $37$ (respectively $113$), we can also conclude that $n$ is not a square modulo $37$ (respectively $113$).

To summarize, given an integer which is not divisible by both $37$ and $113$ we can immediately pick out one of the two forms which cannot possibly represent that integer.

Second part of the plan

If we can find integers $B$ and $C$ such that $nx^2 + Bxy + Cy^2$ is primitive (this is important) and has discriminant $16724$, then we have basically showed that $n$ is represented by one of the two forms listed by the applet. When can we find such $B$ and $C$? We need $$ B^2 - 4nC = 16724 = 2^2 \cdot 37 \cdot 113. $$ In other words, we need to solve the congruence equation $B^2 \equiv 2^2 \cdot 37 \cdot 113 \pmod{4n}$. This is equivalent to solving $B_0^2 \equiv 37 \cdot 113 \pmod{n}$.

If we assume that $n$ is not divisible by $113$, then the conditions stated in the question implies that the congruence equation is solvable. More specifically, the third equation implies that $(37 \cdot 113)c^2 \equiv 113^2 \pmod{n}$ has a solution in $c$. The only possible common factor between $c$ and $n$ is $113$, so by our assumption, $c$ is relatively prime to $n$. Therefore $$ (113 \cdot c^{-1})^2 \equiv 37 \cdot 113 \pmod{n} $$ gives us a solution of the congruence equation we need to construct a form of discriminant $16724$ which represents $n$.

How can be be sure that the form we constructed is primitive? If $n$ is even, what is there to prevent both $B$ and $C$ to be even as well? We will deal with this issue by showing that subject to congruence conditions given in the question, an even $n$ is never represented by any of the two non-primitive forms of discriminant $16724$.

We can carry out an analysis similiar to what we did above to show that if $\frac{n}{2}$ is represented by a form of discriminant $4181$, then we must be able to solve the congruence equation $$ B^2 \equiv 37 \cdot 113 \pmod{4 \cdot \frac{n}{2}}. $$ There is no hope if $n$ is divisible by $4$, because $37 \cdot 113$ is simply not a square modulo $8$. So the question now is whether the three congruence equations forces an even $n$ to be divisible by $4$.

Let us assume to the contrary, that there is an even $n$ which is not divisible by $4$. We will write $n = 2n_{0}$, where $2 \nmid n_{0}$. We can check that $$ \left( \frac{37a^2}{113} \right) = \left( \frac{-113b^2}{37} \right), $$ so $n$ is simultaneously a square or a non-square modulo $37$ and $113$. Therefore $$ \left( \frac{2n_{0}}{113} \right) = \left( \frac{2n_{0}}{113} \right) \implies \left( \frac{n_{0}}{113} \right) = - \left( \frac{n_{0}}{37} \right) \implies \left( \frac{113}{n_{0}} \right) = - \left( \frac{37}{n_{0}} \right) $$ by properties of the Jacobi symbol, with the last implication exploiting the fact that $n_{0}$ is odd. This contradicts the third congruence equation in the question.

I think this is the only section where I assume that $37 \nmid n_{0}$.

Putting everything together

We have seen that if $113 \nmid n$, then $n$ is primitively represented by one of the two forms. Now the question is which one. From the first part of the plan, we know that this depends on whether $n$ is a square modulo $113$. Since $37$ is not a square modulo $113$, the first equation in the question implies that $n$ is not a square modulo $113$. Therefore $n$ must be an integer represented by $5x^2 + 122xy - 92y^2$.

To finish things off, we just need to verify that $37x^2 - 113y^2$ is equivalent to $5x^2 + 122xy - 92y^2$. It suffices to check, that $1$ is represented by $x^2 + 128xy -85y^2$ but not by $37x^2 - 113y^2$.

Other comments

We cannot always separate classes of forms using only congruence conditions on the integers they represent, but this modest idea is the starting point of genus theory. Dirichlet's Lectures on Number Theory has a very down-to-earth introduction to this. If you prefer a more modern presentation in terms of abstract algebra, you may want to also look at Flath's Introduction to Number Theory.

The congruence conditions given in the question turn out to be sufficient to guarantee the existence of a form of discriminant $16724$ whose first coefficient is $n$. Suppose we do not have any of those congruence conditions, and we want to try to classify integers $n$ represented by $37x^2 - 113y^2$. It would be nice if we could say that there is a form of the same discriminant with $n$ as the first coefficient; as we have seen above, this immediately gives some necessary conditions that $n$ must satisfy.

There is a standard trick which does just this, assuming that $n$ is primitively represented. An integer $n$ is primitively represented by a form $ax^2 + bxy + cy^2$ if there are relatively prime integers $x_0$ and $y_0$ such that $ax_0^2 + bx_0 y_0 + cy_0^2 = n$. Since $x_{0}$ and $y_{0}$ are relatively prime, we can find integers $\alpha$ and $\beta$ such that $x_{0} \beta - y_{0} \alpha = 1$. Now we have $$ \begin{pmatrix} x_{0} & \alpha \\ y_{0} & \beta \end{pmatrix}^{t} \begin{pmatrix} a & \frac{b}{2} \\ \frac{b}{2} & c \end{pmatrix} \begin{pmatrix} x_{0} & \alpha \\ y_{0} & \beta \end{pmatrix} = \begin{pmatrix} n & \ast \\ \ast & \ast \end{pmatrix}. $$