Intuition for a formula that expresses the class number of an imaginary quadratic field by counting quadratic residues 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?
 A: Update: more thoughts, including a shorter and more nonsensical "proof", on my blog. 

Orde's paper, "On Dirichlet's Class number formula", gives a beautiful nonsense proof, before giving a rigorous one. Thanks to KConrad for pointing out Orde's paper to me. Orde is a little terse, so let me expand:

Let $R$ be the ring of integers in $\mathbb{Q}[\sqrt{-p}]$. For simplicity, take $p>3$. For any positive integer $N$, let $S(N)$ be the number of ideals in $R$ with norm $N$. By unique factorization into prime ideals and a little thought, we have
$$S(N) = \sum_{d|N} \left( \frac{-p}{d} \right). \quad (*)$$
This formula is correct for $N>0$. Orde explains how to extend this formula to be correct for $N \neq 0$. The formula at $N=0$ will then be the class number formula!
Let $C$ be the class group of $R$. Let $Q$ be the set of integral quadratic forms with discriminant $-p$, modulo equivalence. Note that $Q$ is the disjoint union of $Q^{+}$ and $Q^{-}$; the positive definite forms and the negative definite ones. For most purposes, we discard $Q^{-}$, but today we want it around. There is a standard bijection between $C$ and $Q^{+}$. 
For $c \in C$ and $N>0$, let $S_c(N)$ be the number of ideals of $R$ of class $c$ and norm $N$. So $S(N)=\sum_{c \in C} S_c(N)$. Let $q$ be the corresponding positive definite form and let $T_q(N)$ be the number of representations of $N$ be the form $q$. By the standard relationship between quadratic forms and ideals, $T_q(N)=2 S_c(N)$. (That $2$ is because $R$ has $2$ units.) Also, since $N>0$, we have $T_{-q}(N)=0$. So
$$\frac{1}{2} \sum_{q \in Q} T_q(N) = S(N) = \sum_{d|N} \left( \frac{-p}{d} \right) \quad (**).$$
The left and right hand sides of $(**)$ are symmetric in exchanging $N$ and $-N$, so $(**)$ is also valid for $N<0$.
Now, consider $(**)$ for $N=0$. For any $q \in Q$, we have $T_q(0)=1$, since $q$ is either positive or negative definite. So the left hand side is $(1/2) |Q|=|C|$. 
Everything divides $0$, so the right hand side is $\sum_{d>0} \left( \frac{-p}{d} \right)$. That doesn't converge, but its Cesaro sum is $(1/p) \sum_{d=1}^{p} (p-d) \left( \frac{-p}{d} \right).$ (If we were doing the case that $p \equiv 1 \mod 4$, that average would be over $4p$ terms, instead of just $p$ of them.) So we "derive" that
$$|C| = (1/p) \sum_{d=1}^{p} (p-d) \left( \frac{-p}{d} \right).$$
This is easily shown to be equivalent to the class number formula.
A: I'll have to be brief; I can think of two reasons "why":


*

*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.

*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.
A: This question was asked recently.  Take a look at 
Most squares in the first half-interval
for some further references.  In Ireland & Rosen p. 225 (notes to Chapter 14) they say that the difference formula annihilating the class group (as an exponent) goes back to Kummer.
