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
 
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Back
Top