I was just solving some congruence problems with prime modulo. Such as this one:
[tex]x^2equiv 59(mod 11)[/tex]
I was using Quadratic Residues to determine whether or not my equations had solutions. For example, in the case above, I would write out the quadratic residues of 11:
[tex]QR_{11} = {1,3,4,5,9}[/tex]
Here I noted that if my modulo was prime then the number of quadratic residues is always less than half the prime. So in this case, 11/2 = 5.5 and there are 5 QR's.
Then I would use the Legendre symbol:
[tex](59/11) = (4/11) = 1 quadquadmbox{since 4 is a quadratic residue of 11}[/tex]
Which tells me that my equation has a solution. But notice that I needed to calculate all the quadratic residues first.
So then I came across the Quadratic Reciprocity Law which said that if p and q are primes then
[tex](p/q) = -(q/p)[/tex]
if [itex]p,qequiv 3(mod 4)[/itex], otherwise [itex](p/q) = (q/p)[/itex].
So, this tells me that solving an equation such as [itex]x^2equiv p(mod q)[/itex] is exactly the same as solving [itex]x^2 equiv q(mod p)[/itex], UNLESS p or q is congruent to 3 modulo 4.
EX1. In modulo 5, we have 1 and 4 as quadratic residues. Then (5/97) = (97/5) because neither 5 nor 97 are congruent to 3 modulo 4. So then (5/97) = (97/5) = (2/5) = -1 since 2 is not a QR of 5.
EX2. (85/97) = (5/97)(17/97) {by a corollary of the QRL} = (97/5)(97/17) {since neither 5 nor 17 are congruent to 3 modulo 4} = (2/5)(12/17) {simplifying in mod 17} = (-1)(-1) = 1. Since the QR's of 17 are 1,2,4,8,9,13,15,16, and 12 is not a QR of 17.
My question is: why is what I've written in bold true? Why aren't those two equations equivalent if p or q is congruent to 3 modulo 4? What is so special about 3 modulo 4?