MHB Can someone give a simple explanation of quadratic residues?

AI Thread Summary
A quadratic residue mod n is defined as a number q for which there exists an integer x such that x^2 ≡ q (mod n). To determine if a number is a quadratic residue, one can calculate k^2 mod n for integers k from 0 to ⌊(n-1)/2⌋, identifying which results are quadratic residues. For example, 8 is a quadratic residue mod 17 because 5^2 ≡ 8 (mod 17), while it is a nonresidue mod 11 as there are no integers x satisfying x^2 ≡ 8 (mod 11). The discussion also confirms the quadratic residues for mod 13 and mod 23, affirming the understanding of the concept. Understanding quadratic residues is essential for various applications in number theory and cryptography.
Terry1
Messages
4
Reaction score
0
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
 
Mathematics news on Phys.org
Terry said:
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
 
Last edited:
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
 
Terry said:
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
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Back
Top