Quadratic residues

  • Thread starter moriheru
  • Start date
  • #1
272
17
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.
 

Answers and Replies

  • #2
FeDeX_LaTeX
Gold Member
437
13
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.
 
  • Like
Likes moriheru
  • #3
272
17
Thanks but how does one get to the p/2-1/2?
 
  • #4
FeDeX_LaTeX
Gold Member
437
13
There is a nice proof on the first page of this document -- see Proposition 1.2.
 
  • Like
Likes moriheru

Related Threads on Quadratic residues

Replies
2
Views
452
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
3
Views
781
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
4
Views
6K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
7
Views
676
Top