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?
$$\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$.