The general theorem is: for all odd, distinct primes $p, q$, the following holds: $\left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}$
I've discovered the following proof for the case $q=3$: Consider the Möbius transformation $f(x) = \frac{1}{1-x}$, defined on $F_{p} \cup {\infty}$. It is a bijection of order 3: $f^{(3)} = Id$.
Now we'll count the number of fixed points of $f$, modulo 3:
1) We can calculate the number of solutions to $f(x) = x$: it is equivalent to $(2x-1)^2 = -3$. Since $p \neq 2,3$, the number of solutions is $\left( \frac{-3}{p} \right) + 1$ (if $-3$ is a non-square, there's no solution. Else, there are 2 distinct solutions, corresponding to 2 distinct roots of $-3$).
2) We know the structure of $f$ as a permutation: only 3-cycles or fixed points. Thus, number of fixed points is just $|F_{p} \cup {\infty}| \mod 3$, or: $p+1 \mod 3$.
Combining the 2 results yields $p = \left( \frac{-3}{p} \right) \mod 3$. Exploiting Euler's criterion gives $\left( \frac{p}{3} \right) = p^{\frac{3-1}{2}} = p \mod 3$, and using $\left( \frac{-1}{p} \right) = (-1)^{\frac{p-1}{2}}$, we get: $\left( \frac{3}{p} \right) \left( \frac{p}{3} \right) = (-1)^{\frac{p-1}{2}\frac{3-1}{2}} \mod 3$ and equality in $\mathbb{Z}$ follows.
My questions:
- Can this idea be generalized, with other functions $f$?
- Is there a list\article of proofs to special cases of the theorem?