Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

What is so special about 3(mod4)?

  1. Jun 12, 2006 #1
    I was just solving some congruence problems with prime modulo. Such as this one:

    [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?
    Last edited: Jun 12, 2006
  2. jcsd
  3. Jun 12, 2006 #2
    PART 2:
    Now I've just had a look at Gauss's Lemma. For those who dont 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, [itex]x^2\equiv a(\mod p)[/itex] 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 [itex]x^2\equiv 7(\mod 13)[/itex] exists if the number of residues of S greater than p/2 is even. So

    [tex]S = \{7,14,21,28,35,42\}[/tex]

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

    [tex]S' = \{1,2,3,7,8,9\}[/tex]

    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) [tex]x^2\equiv 7(\mod 13)[/tex] has no solution. And
    2) [tex](7/13) = -1[/tex]
  4. Jun 12, 2006 #3
    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.
  5. Jun 12, 2006 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.

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

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

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

    which is easy to prove by contradiction.
  6. Jun 13, 2006 #5
    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). Im 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. [itex](a^2/p) = +1[/itex] 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 [itex]x^2\equiv 90(\mod 127)[/itex] has no solution.

    Are all of my statements correct?
  7. Jun 13, 2006 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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}

    that is not a corollary of the QRT. it is just obvious since a square in the integers is obviously a square modulo anything.
  8. Jun 13, 2006 #7


    User Avatar
    Science Advisor
    Homework Helper

    An equivalent statement of the Quadratic reciprocity theorem is:


    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)

    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)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook