# Legendre symbol question without Euler's Criterion

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

$$\left(\dfrac{10}{41}\right)$$

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?

• Well, do you know how to compute $\left( \frac 2{41}\right)$? – lulu Apr 11 '18 at 21:11
• Of course. $\left(\dfrac{2}{41}\right) = 1$ since $41 \equiv 1$ (mod $8$). – John Smith Apr 11 '18 at 21:13
• Good. So your expression is just $\left( \frac 5{41}\right)$. Reciprocity then settles the point instantly. – lulu Apr 11 '18 at 21:15
• 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.$ – John Smith Apr 11 '18 at 21:18
• 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}$ – 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$.