1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Quadratic residues

  1. Apr 5, 2015 #1
    This may be a bit vague but can anyone explain this sentence to me
    http://en.wikipedia.org/wiki/Quadratic_residue:"Modulo 2, every integer is a quadratic residue.

    Modulo an odd prime number p there are (p + 1)/2 residues (including 0) and (p − 1)/2 nonresidues."

    If this is to vague I apologize.
     
  2. jcsd
  3. Apr 5, 2015 #2

    FeDeX_LaTeX

    User Avatar
    Gold Member

    As in the link above, an integer a is a quadratic residue modulo p if it's congruent to a square mod p. In other words, the congruence [itex]x^2 \equiv a \text{ }\left( \text{mod } p \right)[/itex] has a solution. Some like to add that a needs to be invertible, since 0 is trivially a quadratic residue. The first line says that every integer a satisfies the congruence [itex]x^2 \equiv a \text{ }\left( \text{mod } 2 \right)[/itex]. This isn't surprising: if a is 0 or 1 modulo 2, there will always be a solution (just take x to be 0 or 1 respectively).

    The second line is saying that the congruence [itex]x^2 \equiv a \text{ }\left( \text{mod } p \right)[/itex] for p ≠ 2 has [itex]\frac{p+1}{2}[/itex] integer values of a for which that congruence holds, and [itex]\frac{p-1}{2}[/itex] integer values of a for which it doesn't.

    For example, take p = 7. The squares mod 7 are 0, 1, 2, 4, so the quadratic residues mod 7 are 0, 1, 2 and 4. The quadratic non-residues are 3, 5 and 6, because you can't find an integer that squares to give 3, 5 or 6, modulo 7.
     
  4. Apr 5, 2015 #3
    Thanks but how does one get to the p/2-1/2?
     
  5. Apr 5, 2015 #4

    FeDeX_LaTeX

    User Avatar
    Gold Member

    There is a nice proof on the first page of this document -- see Proposition 1.2.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Quadratic residues
  1. A quadratic polynomial? (Replies: 19)

  2. Factorising a quadratic? (Replies: 19)

  3. Quadratic polynomials (Replies: 5)

Loading...