If we have distinct primes $p \equiv q \equiv 1 \pmod 4,$ with Legendre $(p|q) = (q|p) = -1,$ there is a solution to $u^2 - pq v^2 = -1$ in integers and the fundamental unit of $O\_{\mathbb Q(\sqrt{pq})} $ has norm $-1.$ Stevenhagen attributes this to Dirichlet (1834).


There is no such result for $p \equiv q \equiv 1 \pmod 4,$ with Legendre $(p|q) = (q|p) = 1.$ I did a census, out of the first 300,000 such numbers, there were 99284 for which $u^2 - pq v^2 = -1$ was possible, or very close to one out of three. Here are the first 100 such, and the first 200 not:



```
    145    445    901   1145   1313   1745   2249   2305   2501   2545
   2605   2705   3029   3161   3341   3545   3601   3845   4045   4777
   5045   5245   5305   5545   5629   5713   5933   6145   6245   6401
   6445   6649   6757   6893   6953   6989   7045   7093   7397   7745
   7837   7897   8005   8077   8345   8545   8653   8945   9089   9305
   9673   9881   9953  10001  10081  10145  10345  10405  10445  10777
  10817  10961  11029  11141  11237  11453  11629  11729  11945  12181
  12389  12461  12629  12773  12961  13105  13169  13549  13645  13801
  14305  14933  15245  15397  15445  15509  15529  15845  15929  15949
  16153  16601  16609  16645  16801  16837  16861  16945  17305  17345

```

================================



```
    205    221    305    377    505    545    689    745    793    905
   1205   1345   1405   1469   1513   1517   1537   1717   1945   1961
   2005   2041   2045   2105   2245   2329   2353   2533   2669   2701
   2845   2993   3005   3205   3305   3497   3505   3737   3805   3893
   4069   4105   4145   4321   4369   4381   4405   4453   4633   4645
   4705   4717   4849   4981   5017   5057   5069   5105   5141   5249
   5345   5513   5645   5809   5905   5917   5989   6001   6005   6341
   6497   6505   6605   6613   6697   6773   6805   6905   7081   7145
   7157   7289   7361   7405   7445   7453   7769   7813   7957   8033
   8045   8105   8149   8333   8357   8473   8489   8605   8621   8633
   8705   8749   8801   9005   9077   9113   9445   9469   9505   9701
   9745   9797   9809   9841  10121  10237  10361  10421  10441  10517
  10573  10645  10705  10805  10841  10877  11105  11345  11357  11405
  11513  11545  11705  11905  11917  12017  12137  12205  12317  12469
  12605  12745  12869  12913  12937  13045  13073  13141  13213  13253
  13445  13637  13705  13745  13817  13837  13897  13945  13969  13973
  14005  14093  14209  14257  14309  14417  14473  14521  14545  14689
  14701  14761  14845  14893  14989  15005  15109  15205  15293  15305
  15545  15605  15677  15769  15857  15905  16021  16045  16105  16145
  16201  16237  16409  16441  16505  16769  16805  16913  17113  17197

```

============


Note that you can quickly check the above at <http://www.numbertheory.org/php/unit.html>


Question: in the limit, do exactly one third of such $n=pq,$ with $p \equiv q \equiv 1 \pmod 4,$ and Legendre $(p|q) = (q|p) = 1,$ allow $u^2 - pq v^2 = -1?$ Or, more to the point I suppose, $x^2 + xy - \frac{pq-1}{4} y^2 = -1?$



Fundamental units with norm $-1$ in real quadratic fields
Stevenhagen "[The number of real quadratic fields having units of negative norm](http://projecteuclid.org/euclid.em/1048516217)" Exp Math 1993 makes the following analysis (last paragraph page 127):


Let $D>0$. Let $C$ be the narrow class group of $\mathbb{Q}(\sqrt{D})$ (ideals modulo principal ideals whose generator has positive norm). Then the ideal $(\sqrt{D})$ is $2$-torsion in $C$. There is a unit $\epsilon$ of norm $-1$ if and only if $(\sqrt{D})$ is trivial in $C$ (as, in that case, $\epsilon \sqrt{D}$ generates the same ideal.


Let $D=pq$ with $p \equiv q \equiv 1 \bmod 4$. Saberhagen computes that the $2$-torsion $C[2]$ is isomorphic to $\mathbb{Z}/2$. The primes $(p)$ and $(q)$ ramify, and $C[2]$ is generated by the classes of the ideals $\mathfrak{p}$ and $\mathfrak{q}$ lying over $p$ and $q$. Thus, we have a surjection $(\mathbb{Z}/2)^2 \to \mathbb{Z}/2$ sending $(a,b)$ to the class of $\mathfrak{p}^a \mathfrak{q}^b$ in $\mathbb{Z}/2$. We want the probability that $(1,1)$ is in the kernel of this surjection.


If we choose a random surjection $(\mathbb{Z}/2)^2 \to \mathbb{Z}/2$, the odds that $(1,1)$ is in the kernel are $1/3$, which recovers Will's guess. Stevenhagen reports that numerical data is consistent with the hypothesis that the surjection is randomly chosen.




---


I've been thinking about this, and I think that I can state Stevenhagen's conjecture in a fully elementary way. (No idea about a proof, of course.) Fix a $t \times t$ symmetric matrix $A$ over $\mathbb{F}\_2$ whose rows sum to $0$. Consider $t$-tuples of primes $(p\_1,p\_2,\ldots,p\_t)$ such that all $p\_i \equiv 1 \bmod 4$ and $\left( \frac{p\_i}{p\_j} \right) = (-1)^{A\_{ij}}$ for $i \neq j$. Let $D =p\_1 \cdots p\_t$ and let $(x,y)$ be the primitive solution to Pell's equation $x^2-D y^2=1$. Then $x \equiv (-1)^{b\_i} \bmod p\_i$ for some vector $b \in \mathbb{F}\_2^t$. I will prove below that $b$ is a nonzero element in the kernel of $A$. Stevenhagen's conjecture is equivalent to saying that all nonzero elements of $\mathrm{Ker}(A)$ occur with equal probability, as $(p\_1, \ldots, p\_t)$ runs over primes obeying $\left( \frac{p\_i}{p\_j} \right) = (-1)^{A\_{ij}}$. 


The negative Pell equation is solvable if and only if $b=(1,1,\ldots,1)$. (In other words, $x \equiv -1 \bmod D$.) So if $t=2$ and $\left( \frac{p\_1}{p\_2} \right)=-1$, then $b$ must be the unique element of $\mathrm{Ker} \left( \begin{smallmatrix} 1 & 1 \\ 1 & 1 \end{smallmatrix} \right)$ and the negative Pell equation is solvable but, if $\left( \frac{p\_1}{p\_2} \right)=1$, then $b$ could be any of the $3$ nonzero elements of $\mathrm{Ker} \left( \begin{smallmatrix} 0 & 0 \\ 0 & 0 \end{smallmatrix} \right)$ and the negative Pell equation is solvable with probability $1/3$.


It looks like dealing with primes that are $2$ or $3 \bmod 4$ is just more bookkeeping, but you didn't ask, so I won't do it.




---


I will now explain some of the above claims. First, by a computation modulo $4$, note that $x$ is odd and $y$ is even. 


Put $P = \prod\_{b\_i=1} p\_i$ and $Q = \prod\_{b\_i=0} p\_i$, so $D=PQ$. So $x \equiv -1 \bmod P$ and $x \equiv 1 \bmod Q$. We have
$$\left( \frac{x+1}{2P} \right) \left( \frac{x-1}{2 Q} \right) = \left( \frac{y}{2} \right)^2$$
where all factors are integers.


The factors on the left are relatively prime, since
$$P \left( \frac{x+1}{2P} \right) - Q \left( \frac{x-1}{2 Q} \right)=1.$$
So $(x+1)/(2P)=u^2$ and $(x-1)/(2Q)=v^2$ for some $u$ and $v$. We deduce that
$$P u^2 - Q v^2 = 1. \quad (\ast)$$


We can now see that $b \neq 0$: If $b=0$ then $P=1$ and $Q=D$, so $(\ast)$ contradicts the minimality of $(x,y)$.


We now check that $Ab=0$, by computing each coordinate $\sum\_j A\_{ij} b\_j$ of $Ab$. 


**Case 1** $b\_i=0$. Then $p\_i$ divides $Q$ and, reducing $(\ast)$ modulo $p\_i$, we see that $\prod\_{b\_j=1} p\_j$ is square modulo $p\_i$. This exactly says that $\sum\_{j} A\_{ij} b\_j=0$.


**Case 2** $b\_i=1$. As above, we deduce that $\prod\_{b\_j=0} p\_j$ is square modulo $p\_i$, so $\sum\_{j \neq i} A\_{ij} (1-b\_j)=0$. But this is $\sum\_{j \neq i} A\_{ij} + \sum\_{j \neq i} A\_{ij} b\_j = A\_{ii} + \sum\_{j \neq i} A\_{ij} b\_j = \sum\_j A\_{ij} b\_j$, where the first equality is because the rows of $A$ sum to $0$.


Finally, note that, if $b=(1,1,\cdots, 1)$, then $(\ast)$ says that the negative Pell's equation is solvable. Conversely, if the negative Pell's equation is solvable with solution $v^2-D u^2 = -1$, then $(x,y) = (v^2+Du^2, 2 uv)$ is the minimal solution to $x^2-Dy^2=1$ and, sure enough, $x \equiv v^2 \equiv -1 \bmod D$.


