I would like to solve the following Legendre symbol problem without the use of Euler's Criterion. We have the following:


We can do it the long way and write out a table modulo $41$ and see if $10$ is a quadratic residue (or a nonresidue) modulo $41$. But, are there more ways to approach this question so that I don't need to write out the table?

  • $\begingroup$ Well, do you know how to compute $\left( \frac 2{41}\right)$? $\endgroup$ – lulu Apr 11 '18 at 21:11
  • $\begingroup$ Of course. $\left(\dfrac{2}{41}\right) = 1$ since $41 \equiv 1$ (mod $8$). $\endgroup$ – John Smith Apr 11 '18 at 21:13
  • $\begingroup$ Good. So your expression is just $\left( \frac 5{41}\right)$. Reciprocity then settles the point instantly. $\endgroup$ – lulu Apr 11 '18 at 21:15
  • $\begingroup$ Then, we have $\left(\dfrac{5}{41}\right) = \left(\dfrac{41}{5}\right) = 1$ since $41 \equiv 1$ (mod $5$). So $\left(\dfrac{10}{41}\right) = 1.$ $\endgroup$ – John Smith Apr 11 '18 at 21:18
  • 1
    $\begingroup$ Perfect. Well, you should note that one (actually both) of $5, 41$ are $\equiv 1 \pmod 4$. Anyway, once you get your answer it is trivial to check it by the method you mentioned. Indeed, $16^2\equiv 10 \pmod {41}$ $\endgroup$ – lulu Apr 11 '18 at 21:20

$$\left(\frac{10}{41}\right)=\left(\frac{2^2\cdot 10}{41}\right) = \left(\frac{-1}{41}\right) = (-1)^{\frac{41-1}{2}} = 1.$$ Outcome: $10$ is a quadratic residue $\!\!\pmod{41}$.
Alternative: in $\mathbb{F}_{41}^*$ there are both an element $\alpha$ of order $8$ and an element $\beta$ of order $5$.
On the other hand $0=\alpha^2+\frac{1}{\alpha^2}=\left(\alpha+\frac{1}{\alpha}\right)^2-2$ and $$0=4\left(\beta^2+\beta+1+\frac{1}{\beta}+\frac{1}{\beta^2}\right)=\left(2\beta+1+\frac{2}{\beta}\right)^2-5$$ imply that both $2$ and $5$ are quadratic residues $\!\!\pmod{41}$, and so it is $10$.


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.