1. Not finding help here? Sign up for a free 30min 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 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,
    [​IMG]
    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: Jan 23, 2008
  2. jcsd
  3. Jan 23, 2008 #2

    NateTG

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

    Now:
    [tex]n^2=(11k+r)^2=121k+22kr+r^2=11(11k+2kr)+r^2=11k_2+r^2[/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

    Dick

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Quadratic residues modulo p
  1. Quadratic Residues (Replies: 51)

Loading...