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.

  • 1
    $\begingroup$ 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 $\endgroup$ – Maik Pickl Jan 30 '18 at 21:52
  • $\begingroup$ @MaikPickl Thank you, but I don't know how to prove this theorem. $\endgroup$ – mathcourse Jan 30 '18 at 22:06
  • $\begingroup$ @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 $\endgroup$ – Will Jagy Jan 31 '18 at 21:14
  • 1
    $\begingroup$ @WillJagyI know! My comments above refer to the original version, in which the equation was (mistakenly) written as $x^2+dy^2=-1$ :- $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ How do we get that $p = a^2+b^2$? $\endgroup$ – mathcourse Jan 31 '18 at 8:15
  • $\begingroup$ @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/… $\endgroup$ – Mr Pie 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.

enter image description here enter image description here enter image description here

| cite | improve this answer | |

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.