Determine the number of quadratic residues of the following primes:
(a) 1223
(b) 3571
(c) 104 729
(d) 179 424 673
We'll be using Proposition (7.4).
Let $p$ be an odd prime. Then there are exactly $\frac{p-1}{2}$ quadratic residues, and $\frac{p-1}{2}$ quadratic non-residues of $p$.
(a) The prime 1223 has $\frac{1223-1}{2} = 611$ quadratic residues.
(b) The prime 3571 has $\frac{3571-1}{2} = 1785$ quadratic residues.
(c) The prime 104729 has $\frac{104729-1}{2} = 52364$ quadratic residues.
(d) The prime 179424673 has $\frac{179424673-1}{2} = 89712336$ quadratic residues.