Because it is enough to calculate these values to find the quadratic residue $x^2 ≡ a (mod 13)$

29 Views Asked by At

Let $m$ be a positive integer and $a$ any integer such that $(a, m) = 1$. Then $a$ is a quadratic residue of $m$ if the congruence $x^2 ≡ a (mod m)$ is solvable; otherwise, it is a quadratic nonresidue of $m$. For example if we want to find the quadratic residues of $m = 13$, we calculated $x^2 ≡ a (mod 13)$ with $x=1,2,3,4,5,6,7,8,9,10,11,12$ and we will find that the quadratic residues are $a = 1, 3, 4, 9, 10,12$. If we continue calculating for $x=14$, $x=15$ and so on, we notice that the residuals will be repeated $a=1$, $a=4$ and so on,I wanted to know why this happens? Why is it enough to calculate the squares of numbers $x=1,2,3,4,5,6,7,8,9,10,11,12$ only?