Can someone give a simple explanation of quadratic residues?

[Terry1]

Hi,

This is not coursework, just private study.

Ok, I understand that q is a quadratic residue MOD n if x^2 = q MOD n

What I don't understand is how to figure this out?

I read a paper that states "8 is a quadratic residue mod 17, since 5^2 = 8 MOD 17", fair enough.
It then goes on to state that "8 is a quadratic nonresidue mod 11, because x^2 = 8 MOD 11 has no solutions"

How do we know there are no solutions?

Thanks

 

[kaliprasad]

Hi,

This is not coursework, just private study.

Ok, I understand that q is a quadratic residue MOD n if x^2 = q MOD n

What I don't understand is how to figure this out?

I read a paper that states "8 is a quadratic residue mod 17, since 5^2 = 8 MOD 17", fair enough.
It then goes on to state that "8 is a quadratic nonresidue mod 11, because x^2 = 8 MOD 11 has no solutions"

How do we know there are no solutions?

Thanks

To find if a number is quadratic residue mod x we need to take the numbers k from 0 to x-1 and find

$k^2\,mod\,$ and this shall be a quadratic residue
but because of symmetry as $n^2= (-n)^2$ we need to take k from 0 to $\lfloor\dfrac{x-1}{2}\rfloor$

the numbers we find in above from 0 to n-1 (0 and 1 are always there) are quadratic residue and that are not there are quadratic non residue

for example $0^2 = 0\,mod \, 3$
$1^2 = 1\,mod \, 3$
$2^2 = 1\,mod \, 3$ ( same are 1)
so 0 and 1 are quadratic residue mod 3 but 2 is not quadratic residue

 

[Terry1]

Thanks kaliprasad.

Let's see if I have understood correctly...

From what you explained would I be right in saying {0, 1, 3, 4, 9, 10, 12} are quadratic residues MOD 13
and {0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18} are quadratic residues MOD 23?

Many thanks,

Terry

 

[kaliprasad]

Thanks kaliprasad.

Let's see if I have understood correctly...

From what you explained would I be right in saying {0, 1, 3, 4, 9, 10, 12} are quadratic residues MOD 13
and {0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18} are quadratic residues MOD 23?

Many thanks,

Terry

right