What is so special about 3(mod4)?

[Oxymoron]

I was just solving some congruence problems with prime modulo. Such as this one:

$$x^2\equiv 59(\mod 11)$$

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:

$$QR_{11} = \{1,3,4,5,9\}$$

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:

$$(59/11) = (4/11) = 1 \quad\quad\mbox{since 4 is a quadratic residue of 11}$$

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

$$(p/q) = -(q/p)$$

if $p,q\equiv 3(\mod 4)$, otherwise $(p/q) = (q/p)$.

So, this tells me that solving an equation such as $x^2\equiv p(\mod q)$ is exactly the same as solving $x^2 \equiv q(\mod p)$, 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?

 

[Oxymoron]

PART 2:
Now I've just had a look at Gauss's Lemma. For those who don't recall:

Let p be an odd prime and gcd(a,p) = 1. Let n be the number of residues of the set S = {a,2a,3a,...,(p-1)/2*a} (half the multiples of a) which are greater than p/2. Then (a/p) = (-1)^n.

This lemma tells me that the solvability of a quadratic congruence equation, $x^2\equiv a(\mod p)$ depends upon how many residues of the set S greater than p/2 there are!

For example. Say I pick 13 as my prime p and 7 as my integer a. Then a solution for $x^2\equiv 7(\mod 13)$ exists if the number of residues of S greater than p/2 is even. So

$$S = \{7,14,21,28,35,42\}$$

We stop at 42 because (p-1)/2*a = 12/2*7 = 42. Then

$$S' = \{1,2,3,7,8,9\}$$

after reducing modulo 17. Then the number of residues greater than p/2 (or 6.5) is 3 (namely 7,8, and 9). Let n = 3. Then (-1)^n = -1 which means that

1) $$x^2\equiv 7(\mod 13)$$ has no solution. And
2) $$(7/13) = -1$$

 

[Oxymoron]

PART 3:
Here is something really neat! Pick a prime number p. Then choose any two quadratic non-residues of p. Then multiply them together. What do you get? A quadratic residue of p! Wow. I have no idea how to prove it though.

 

[Hurkyl]

3 mod 4 is special because that's what appears in the quadratic recipricosity theorem! It's also a nonresidue mod 4... but maybe Shmoe can give a deeper reason.

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.

That's easy: squaring is a 2-to-1 function.

Here is something really neat! Pick a prime number p. Then choose any two quadratic non-residues of p. Then multiply them together. What do you get? A quadratic residue of p! Wow. I have no idea how to prove it though.

Very easy if you use the algorithm for computing Legendre symbols.

I assert that this fact is the same as:
(non-residue) * (residue) = (non-residue)

which is easy to prove by contradiction.

 

[Oxymoron]

3 mod 4 is special because that's what appears in the quadratic recipricosity theorem! It's also a nonresidue mod 4... but maybe Shmoe can give a deeper reason.

Yes, but why is it in the quadratic reciprocity theorem? I mean, if an integer is congruent to 3 modulo 4 then the integers is always odd. But the same could be said for 5 modulo 6, etc... But as you said, 3 is a nonresidue mod 4, so maybe that has something to do with it. I predict there is more to it though.


I was computing a Legendre symbol today: (90/127) to be exact. In my first step I found this equals (90/127) = (2/127)(5/127)(3^2/127). I am pretty sure I can do that. Now a corollary to the QRT says that if, in the numerator of the Legendre symbol, I have a square (such as in this case), then the symbol equals +1. i.e. $(a^2/p) = +1$ where p is prime.
So (90/127) = (2/127)(5/127)(+1).

Next I computed (5/127). I swapped the numbers around so I could reduce modulo 5 instead of 127, but before I did, I must check if either 5 or 127 is congruent to 3 modulo 4. It just so happens that 127 is congruent to 3 mod 4, But 5 is not. So, my question is: Must 5 and 127 be both congruent or only either? I think they have to be both.

Anyway, I get (5/127) = (127/5) = (2/5) = -1 since 2 is not a QR of mod 5. And finally (2/127) = (127/2) = (1/2) = +1 since 1 is a QR of mod anything.

Therefore (90/127) = (+1)(-1)(+1) = -1. Implying that 90 is NOT a QR of mod 127, and that $x^2\equiv 90(\mod 127)$ has no solution.

Are all of my statements correct?

 

[matt grime]

Yes, but why is it in the quadratic reciprocity theorem? I mean, if an integer is congruent to 3 modulo 4 then the integers is always odd. But the same could be said for 5 modulo 6, etc... But as you said, 3 is a nonresidue mod 4, so maybe that has something to do with it. I predict there is more to it though.

why don't you find a proof of the recitpocity theorem? it might shed some light on the matter for you.

any odd prime is 1 or 3 mod 4. which one it is affects the set of residues exactly because in only one case is -1 a residue mod p (Hint: use the fact that the legendre symbol of -1 is (-1)^{(p-1)/2}

I was computing a Legendre symbol today: (90/127) to be exact. In my first step I found this equals (90/127) = (2/127)(5/127)(3^2/127). I am pretty sure I can do that. Now a corollary to the QRT says that if, in the numerator of the Legendre symbol, I have a square (such as in this case), then the symbol equals +1.

that is not a corollary of the QRT. it is just obvious since a square in the integers is obviously a square modulo anything.

 

[shmoe]

An equivalent statement of the Quadratic reciprocity theorem is:

$$\left(\frac{p}{q}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}\left(\frac{q}{p}\right)$$

Wherever you found Gauss's lemma probably carries on to a proof of quadratic reciprocity and you can see where these exponents came from (or find any of the many, many other proofs)

PART 3:
Here is something really neat! Pick a prime number p. Then choose any two quadratic non-residues of p. Then multiply them together. What do you get? A quadratic residue of p! Wow. I have no idea how to prove it though.

Have you seen Euler's Criteria? q is a quadratic residue mod p if q^((p-1)/2)=1 mod p and a quadratic non-residue if this is -1. Again, a proof will be enlightening. (Hint-the units mod p form a cyclic group under multiplication)