Discovering Quadratic Reciprocity Is there anything similar to this (page written by Field Medalist Timothy Gowers) for quadratic reciprocity ? 
I mean, the link there explains how you can figure out the solution of cubic equation by yourself without having a suddent flash of inspiration/ genius genes. Is there some similar guide for quadratic reciprocity ?

The first part of this paper http://www.math.ubc.ca/~belked/lecturenotes/620E/Frei%20-%20The%20Reciprocity%20Law%20from%20Euler%20to%20Eisenstein.pdf shows you how the QR law was discovered historically and shows the path all the way back to Diophantus. 
It seems that the first question explicitly stated that is equivalent to a case of QR is
p is an odd prime of the form $x^2+ y^2$ with x, y integers $\iff$ p is equal to 1 mod 4. 
This leads to the more general question:
Given $N\in \mathbb{Z}$, describe the primes $p \notin 2$ for which $p = x^2 + Ny^2$. 
This was considered by Fermat and studied carefully by Euler and leads to the full QR theorem whereas the question for sum of two squares leads to the evaluation of the quadratic character of -1 mod p only.
