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!

Homework Help: Quadratic residues modulo p

  1. Jan 23, 2008 #1
    Q: A natural number r between 0 and p-1 is called a quadratic residue modulo p if there exists an integer x such that x^2 is congruent to r modulo p. Find all the quadratic residues modulo 11.

    I attempted to solve this problem by squaring each of the numbers from x=n=0 to x=n=10,
    http://marauder.millersville.edu/~bikenaga/numbertheory/quadres/quadres18.png [Broken]
    So the quadratic residues modulo 11 should be 1,3,4,5,9 (0 is not a natural number), I believe. However, the definition says "...if there exists an integer x such that...", but there are an infinite number of integers, how can I possible square every integer and check all of them out? It may be possible that somewhere out there that there is an integer x which gives a number different from any of 1,3,4,5,9, right?
    Last edited by a moderator: May 3, 2017
  2. jcsd
  3. Jan 23, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    Choose some integer [itex]n[/itex]. Then there is some [itex]k[/itex] such that [itex]n=11k+r[/itex] with [itex]0\leq r < 11[/itex].

    This means that the residue of the square, mod 11, is entirely determined by [itex]r[/itex] and you only need to check 11 possibilities.
  4. Jan 23, 2008 #3
    Why only 11 possibilities? Any further explanation??
  5. Jan 23, 2008 #4


    User Avatar
    Science Advisor
    Homework Helper

    NateTG already told you. The remainder after division by 11 of r determines the remainder after division by 11 of r^2.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook