There are many proofs of this theorem; Gauss came up with 8 all by himself. We present one that doesn't require a great deal of knowledge from other branches of mathematics, though it is still quite technical.
To simplify the notation downstream, let s = (p-1)/2 and t = (q-1)/2. Thus s is half of p and t is half of q, rounded down.
If we knew that the product [q\p]×[p\q] was -1 to the st power, we would be done. That's because st is odd precisely when p and q are 3 mod 4. The two legendre symbols are opposite only when their product is -1, when st is an odd power, when p and q are 3 mod 4. Otherwise the legender symbols are equal. We need to show that [q\p]×[p\q] is -1 to the st power.
Consider the rectangular region of the xy plane where x ranges from 1/2 to p/2 and y ranges from 1/2 to q/2. This region contains st lattice points, i.e. points with integer coordinates.
Draw three parallel lines through this rectangular region, each having slope q/p. The furst runs through the origin, all the way to the point p/2,q/2, which is the upper right corner of our rectangular region. We will call this the main line. Shift this line up 1/2 unit to get the upper line. Shift it down by q/(2p) to get the lower line. For notational convenience, let w = q/(2p). thus the upper line is raised by 1/2 and the lower line is down by w. A fourth line runs parallel to these three, and will be described later.
Let c be the center of the rectangular region. If we spin the plane 180° about c, the rectangle coincides with itself, and lattice points move to lattice points. The latttice point that was at the upper left of the rectangle is now at the lower right, and so on.
Notice that the lower line hits the right edge of the rectangle at y = q/2 - w. This is w below the upper right corner of the rectangle. Meantime the upper line hits the left side of the rectangle at w above the lower left corner. There is a symmetry here. When we rotate the rectangle about its center, the upper and lower lines switch positions. By correspondence, there are as many lattice points above the upper line as there are below the lower line. Their sum is even, so we can subtract it from st without harm. This will not change the pairty of st, or the value (-1)st. We only need look at the two middle strips, bounded by the main line and the upper and lower lines.
We need to show that the product [q\p]×[p\q] is (-1)n, where n is the number of lattice points in the two strips. It would be enough to show that [q\p] is (-1)k and [p\q] is (-1)l, where k counts the points in the upper strip and l counts the points in the lower strip. With k+l = n, the product would then be (-1)n, which is the same as (-1)st, which is what we want.
The problem is symmetric; we can always interchange p and q. If the relationship holds for one strip, it holds for the other strip, simply by exchanging variables. So let's prove it for the upper strip.
At this point we must draw a fourth line, parallel to the other three. Recall that the upper line was produced by shifting the main line up by 1/2. Now shift the main line down by 1/2 to get the fourth line, which I will call the mirror line. For every value of x, the upper and mirror lines have y coordinates that differ by 1, with the main line trapped halfway between. When x is an integer between 1 and s, exactly one lattice point is trapped between the upper and mirror lines. Which points lie above the main line, and which lie below?
None lie precisely on the main line, because p and q are prime, and a lattice point on the main line implies a common factor. Each point is just above or just below. It depends on the remainder when qx is divided by p. Less than half of p and we trap the lattice point below the main line; more than half of p and we trap the lattice point above. Two remainders will never be the same, else q times the difference in x coordinates is divisible by p. Since the difference in x coordinates is less than p, and q is a prime other than p, this is impossible. Similarly, two remainders can't be opposite mod p, else q times the sum of the x coordinates is divisible by p. Let r(x) be the remainder of qx mod p when this remainder is less than half of p, and p - qx mod p when the remainder is more than half of p. Now r(x) is a scaled measure of the vertical distance between the main line and the trapped lattice point. There are s values of r(x), one for each salient x coordinate, and they're all different, and they're all in the range 1 to s.
Let l(x) be the y coordinate of the trapped lattice point at x. Note that the absolute value of qx-pl(x) is always r(x).
The product of r(x) as x runs from 1 to s is s!. At the same time, the product of qx as x runs from 1 to s is qs×s!. We'll consider these products mod p. Remember that qs is the same as [q,p].
Looking mod p, qx is the same as qx-pl(x), which is -r(x) for points above the main line, and r(x) for points below the main line. We said there were k points above the main line, so pull (-1)k out, leaving the product over r(x), which is s!. Therefore [q,p] = (-1)k, where k is the number of points in the upper strip. This completes the proof.
The question is, how did Gauss ever think of this? Got me! I guess the same way Beethoven thought of his 9th symphony.
Reciprocity laws exist for other residues. For instance, if you know that p is a cubic residue mod q, then you also know whether q is a cubic residue mod p. These higher order relationships will not be explored here. I hope I can include these theorems elsewhere, once rings and fields have been established.