# If $x^2-dy^2 = -1$ has a solution in $\mathbb{Z^2}$, then $d$ is the sum of two coprime squares.

I want to prove:

Let $d\in\mathbb{N}$ be square-free.

If $x^2-dy^2 = -1$ has a solution in $\mathbb{Z^2}$, then $d$ is the sum of two coprime squares.

I've already shown, that the equation has no solution if there exists a prime $p$ dividing $d$ with $p\equiv 3 \text{ mod } 4$. I would appreciate any hints.

• If you have already shown that $d$ has no primefactor that is $3$ mod $4$ you can use: en.wikipedia.org/wiki/Sum_of_two_squares_theorem – Maik Pickl Jan 30 '18 at 21:52
• @MaikPickl Thank you, but I don't know how to prove this theorem. – mathcourse Jan 30 '18 at 22:06
• @MarianoSuárez-Álvarez it turns out there is a reasonable question here; the OP added the condition "squarefree" about four hours after I first answered, but it is not necessary. Without that, showing "coprime" is more work – Will Jagy Jan 31 '18 at 21:14
• @WillJagyI know! My comments above refer to the original version, in which the equation was (mistakenly) written as $x^2+dy^2=-1$ :- – Mariano Suárez-Álvarez Jan 31 '18 at 21:22

If $x^2-dy^2=-1$ then,

$$x^2\equiv -1 \pmod p$$ for all primes $p$ which divide $d$. This is equivalent to $p\equiv 1\pmod 4$ which in turn is known to be equivalent to $p=a^2+b^2$. Since this holds for each prime divisor of $d$ it holds also for $d$.

• How do we get that $p = a^2+b^2$? – mathcourse Jan 31 '18 at 8:15
• @mathcourse because every prime $p$ that is $1$ more than a multiple of $4$ is the sum of two squares. Go here for the proof $\longrightarrow$ math.stackexchange.com/questions/594/… and in the first answer, substitute $a=x$ and $b=y$. If you want it to be better explained, go here $\longrightarrow$ en.m.wikipedia.org/wiki/… – Feeds Jan 31 '18 at 9:15

I see: the condition that $d$ be squarefree was added about four hours after I put the majority of this answer. That is, I am allowing $d$ to have prime factors with exponents allowed to be one or larger than one.

Later still: worth pointing out a selection of facts in the other direction. If we have prime $p \equiv 1 \pmod 4,$ then there is an integer solution to $x^2 - p y^2 = -1.$ Proof in Mordell. There are, however, plenty of $d$ that satisfy the conditions but fail: there is no integer solution to $x^2 - 17 y^2 = -1.$ For an example with odd $d,$ there is no integer solution to $x^2 - 205 y^2 = -1.$

Next Day: it is fairly easy, given that $d > 0$ (but not a square) is not divisible by $4$ or by any prime $q \equiv 3 \pmod 4,$ to show that $d$ is the sum of two squares. The hard part, which people seem to be ignoring, is showing that we can arrange $d = u^2 + v^2$ with $\gcd(u,v) = 1,$ meaning $d$ is the sum of coprime squares.

Well, $d$ cannot be divisible by $4$ either.

I had to look for a while to find a correct proof that your $d$ is not just the sum of two squares, it is the sum of two coprime squares. Most books will not show how to do this; I am paraphrasing from Modern Elementary Theory of Numbers, by Leonard Eugene Dickson, especially Theorem 65 on page 63. I am going to discuss many things that will require further study.

We can handle the even case separately, so let $d$ be odd and the product of (possibly several) $p^{e_p,}$ where the prime $p \equiv 1 \pmod 4$ and the exponent $e_p \geq 1.$ An induction argument shows that there is an integer $n > 0$ such that $$n^2 \equiv -1 \pmod d.$$
$$4 n^2 \equiv -4 \pmod d,$$ $$4 n^2 + 4 = d t$$ with integer $t.$ Actually, as $d$ is odd, we see that $t$ is divisible by $4,$ and we may write $$4 n^2 + 4 = 4 d s$$ with integer $s.$ Or, $$4 n^2 - 4 d s = -4.$$ This means that the discriminant of the binary quadratic form $$\langle d, 2n, s \rangle$$ is $-4.$ I should probably add that $\langle a,b,c \rangle$ means the quadratic form $$f(x,y) = a x^2 + b x y + c y^2,$$ with discriminant $$\Delta = b^2 - 4 a c.$$ This means that the form is $SL_2 \mathbb Z$ equivalent ( this is called Gauss reduction) to $\langle 1,0,1 \rangle.$ Should this be unfamiliar, it means there is an integer matrix $R$ of determinant $1,$ $$R = \left( \begin{array}{cc} \alpha & \beta \\ \gamma & \delta \end{array} \right)$$ such that $$R^T H R = I,$$ with $$H = \left( \begin{array}{cc} d & n \\ n & s \end{array} \right)$$ This means that, taking $$Q = R^{-1} = \left( \begin{array}{cc} \delta & -\beta \\ -\gamma & \alpha \end{array} \right)$$ we have $$Q^T Q = H$$ with $\gcd(\gamma, \delta) = 1.$ And, you see, $$\gamma^2 + \delta^2 = d.$$

The even case is just $2d = (\gamma + \delta)^2 + (\gamma - \delta)^2,$ where both numbers are odd.

First of all, thanks for your help! I'm not quite familiar with binary quadratic forms and I think I found a way proving my statement without using it. It would be nice if you could tell me if this proof is correct:

So let $x^2-dy^2=-1$ have a solution in $\mathbb{Z^2}$, then we know that d has no primefactor $p$ that is $p\equiv3 \text{ mod }4$. We can conclude that $d$ is the sum of two squares because the primes $p\equiv3 \text{ mod }4$ occure in the prime factorization of $d$ only with even exponent ($= 0$).

We get $d = a^2+b^2$ for some $a, b \in \mathbb{Z}$. To show that $a^2,b^2$ are copime we use that $d$ is square-free (I'm sorry that I overlooked that condition). Assume, they are not coprime, then there exists a prime $p$ with $p\mid a^2, p\mid b^2$, so $p^2\mid a^2,p^2 \mid b^2$ and therfore $p^2\mid a^2+b^2=d.$ This contradicts the condition, that $d$ is square-free.