though this one may seem a duplicate of - say - this: Determine all primes $p$ for which $5$ is a quadratic residue modulo $p$, well, I have a question. How would you manage the problem of determining the set of odd primes for which a quadratic residue modulo $p$, when $p$ is 'large'. For instance, suppose $p=29$. Then, one applies the quadratic reciprocity law obtaining: $$ \left(\frac{29}{p}\right)=\left(\frac{p}{29}\right)\cdot\left(-1\right)^{\left(p-1\right)\left(29-1\right)/4} $$

So we need to study the following:

  1. the sign of the Legendre symbol, so the values of $p$ modulo $29$
  2. the parity of $\left(-1\right)^{\left(p-1\right)/2}$ modulo 2, or the parity of $p$ modulo $4$

Now, this suggests to consider values of $p$ modulo $29\cdot4=116$ and since $\varphi\left(116\right)=56$, this approach is surely exhaustive, though there must be a more clever, and faster way. Any suggestion?


Since the final answer will necessarily look like "$29$ is a quadratic residue modulo $p$ if and only if $p\mod 116$ is one of the following values ..." a more clever and faster way can hardly be imagined.


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.