Quadratic Residues: Explanation & Modulo Odd Prime Number

[moriheru]

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.

 

[FeDeX_LaTeX]

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 $x^2 \equiv a \text{ }\left( \text{mod } p \right)$ 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 $x^2 \equiv a \text{ }\left( \text{mod } 2 \right)$. 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 $x^2 \equiv a \text{ }\left( \text{mod } p \right)$ for p ≠ 2 has $\frac{p+1}{2}$ integer values of a for which that congruence holds, and $\frac{p-1}{2}$ 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.

 

[moriheru]

Thanks but how does one get to the p/2-1/2?

 

[FeDeX_LaTeX]

There is a nice proof on the first page of this document -- see Proposition 1.2.