Finding Quadratic Residues Modulo 11: Is It Possible to Check All the Integers?

[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,
http://marauder.millersville.edu/~bikenaga/numbertheory/quadres/quadres18.png
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?

 

[NateTG]

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

Now:
n^2=(11k+r)^2=121k+22kr+r^2=11(11k+2kr)+r^2=11k_2+r^2[/itex]<br /> This means that the residue of the square, mod 11, is entirely determined by r and you only need to check 11 possibilities.

 

[kingwinner]

Choose some integer n. Then there is some k such that n=11k+r with 0\leq r &lt; 11.

Now:
n^2=(11k+r)^2=121k+22kr+r^2=11(11k+2kr)+r^2=11k_2+r^2[/itex]<br /> This means that the residue of the square, mod 11, is entirely determined by r and you only need to check 11 possibilities.

<br /> <br /> Why only 11 possibilities? Any further explanation??

 

[Dick]

NateTG already told you. The remainder after division by 11 of r determines the remainder after division by 11 of r^2.