0
$\begingroup$

How many Nonzero quadratic residues are there modulo prime 101

I am lost where to start to my knowledge there is no formula for number of quadratic residues a prime has It will be too much to start checking all numbers from 2 to 100 if they are a quadratic residue or not

Any help appreciated and please also guide me if there is a way to do this for any prime p Thanks

$\endgroup$
1
$\begingroup$

Expanding David's answer, for any $p>2$ the map $\phi:\mathbb{F}_p^*\to\mathbb{F}_p^*$ defined by $\phi(x)=x^2$ sends $y$ and $-y$ into the same element, hence the number of quadratic residues is $\leq\frac{p-1}{2}$. On the other hand, $\mathbb{F}_p^*$ is a cyclic group generated by $g$ with $o(g)=p-1$, hence all the "even powers" of $g$ are quadratic residues, giving that the number of quadratic residues is $\geq\frac{p-1}{2}$.

$\endgroup$
1
$\begingroup$

Modulo a prime (except for $2$), exactly half the non-zero residues are quadratic residues.

$\endgroup$
0
$\begingroup$

Note that if $r\equiv x^2\equiv y^2 \mod p$ then $x^2-y^2=(x+y)(x-y)\equiv 0 \mod p$

Since $p$ is prime, one of the factors $x+y, x-y$ must be divisible by $p$, and this is equivalent to $x\equiv \pm y \mod p$.

Apart from the residue zero, and the case $p=2$ where we have $1=-1$, this gives precisely two square roots for each quadratic residue. The number of square roots is $p-1$ (just square them all), so the number of quadratic residues is $\cfrac {p-1}2$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.