# Quadratic residues modulo p

1. Jan 23, 2008

### kingwinner

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,

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. Jan 23, 2008

### NateTG

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

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 $r$ and you only need to check 11 possibilities.

3. Jan 23, 2008

### kingwinner

Why only 11 possibilities? Any further explanation??

4. Jan 23, 2008

### Dick

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?