If $p$ is a prime of the form $4n+3$, the class number $h$ of $Q[\sqrt{-p}]$ can be expressed using the number $V$ of quadratic residues and $N$ nonresidues in the interval $[1,\frac{p-1}{2}]$: 


* If $p=8n+7$ then $h=V-N$
* If $p=8n+3$ then $h=\frac{1}{3}(V-N)$


This result seems so simple and elegant, but its proof (which I saw in Number Theory by Borevich & Shafarevich - p. 346), while definitely beautiful, is not very short and is based on the analytic class number formula. And so I didn't feel that the proof really helped "demystify" the result.


This leads me to ask: Can someone see intuition for this result? Any short heuristic argument that would lead to it? Any obvious meaning of $h=V-N$? In short, "why" is it true?



Intuition for a formula that expresses the class number of an imaginary quadratic field by counting quadratic residues
I'll have to be brief; I can think of two reasons "why":


1. Cauchy and Jacobi proved that for a prime ideal ${\mathfrak p}$ in a complex quadratic number field with prime discriminant, the h-th power of ${\mathfrak p}$ (with $h$ as in your question) is principal. Their technique was what we nowadays know as the Stickelberger ideal.
You should find references in Ireland-Rosen.
2. Venkov, in the 1920s, gave an arithmetic proof of a large part of Dirichlet's class number formulas based on Gauss's work on ternary quadratic forms and the arithmetic of quaternions. There are modern accounts floating around, and I remember the names Rehm and Shemanske in this connection (if google doesn't help, I'll provide you with references when I'm back from the holidays -). This approach is probably more involved than Dirichlet's, so I don't know whether it explains anything.


EDIT: Let me first give you the references for 2.


* B.A. Venkov, *On the arithmetic of quaternion algebras* (Russ.),
Izv. Akad. Nauk (1922), 205--220, 221--246; ibid. (1929), 489--509, 532--562, 607--622
* H.P. Rehm,  *On a theorem of Gauss concerning the number of solutions
 of the equation $x^2 + y^2 + z^2 = m$*, in "Selected 
 topics on ternary forms and norms" (O. Taussky, ed.), Dekker 1976
* Th.R. Shemanske, *Representations of ternary quadratic forms and the 
 class number of imaginary quadratic fields*,
 Pac. J. Math. {\bf 122} (1986), 223--250


As for 1, let $K/{\mathbb Q}$ be a finite abelian extension with Galois group $G$
and conductor $m$. Let $\sigma\_a$ denote the restriction of the automorphism 
$\zeta\_m \to \zeta\_m^a$ of ${\mathbb Q}(\zeta\_m)$ to $K$. Then
$$ \theta(K) = \frac{1}{m} \sum a\sigma\_a^{-1} \in {\mathbb Q}[G], $$
where the sum is over all $0 < a < m$ with $(a,m) = 1$, is called the *Stickelberger element* corresponding to $K$. The fact that $(b-\sigma\_b)\theta \in {\mathbb Z}[G]$ for integers $b$ coprime to $m$ allows us to define the *Stickelberger ideal*
$I\_0(K)$ as the ideal in ${\mathbb Z}[G]$ generated by elements of the form
$(b-\sigma\_b)\theta$. Set $I(K) = {\mathbb Z}[G] \cap \theta {\mathbb Z}[G]$. 
If $K = {\mathbb Q}(\zeta\_m)$ is a full cyclotomic field, then $I(K) = I\_0(K)$.


Stickelberger's Theorem says that if $K/{\mathbb Q}$ is an abelian extension, then the Stickelberger ideal $I(K)$ annihilates the class group $Cl(K)$.


Applied to quadratic extensions, you get the theorem first proved by Cauchy and Jacobi mentioned above. See my Reciprocity Laws, Chapter 11, for details.


