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...