I was just solving some congruence problems with prime modulo. Such as this one:(adsbygoogle = window.adsbygoogle || []).push({});

[tex]x^2\equiv 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 \quad\quad\mbox{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,q\equiv 3(\mod 4)[/itex], otherwise [itex](p/q) = (q/p)[/itex].

So, this tells me that solving an equation such as [itex]x^2\equiv 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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# What is so special about 3(mod4)?

**Physics Forums | Science Articles, Homework Help, Discussion**