Evaluate the following Legendre symbols using quadratic reciprocity:
- $\left(\frac{295}{401}\right)$
- $\left(\frac{713}{1009}\right)$
I know that can flip the numbers and reduce because both $401$ and $1009$ are equivalent to $1 \pmod{\!p}$ and so on, but I am starting to get weird numbers and I think I did something wrong in one of my steps.
The trick here is going to be to reduce the symbols above into a product of Legendre Symbols. Then one can use the multiplicative properties of the Legendre symbol as well as the theorems giving us values such as $\big(\frac{2}{p}\big)$ and $\big(\frac{1}{p}\big)$. When there is a composite number in the symbol, it is the general Jacobi symbol. So for instance, in the first one: \begin{align} \big(\frac{295}{401}\big) &= \big(\frac{5}{401}\big)\big(\frac{59}{401}\big) \\ &= \big(\frac{401}{5}\big)\big(\frac{401}{59}\big) \\ &= \big(\frac{1}{5}\big)\big(\frac{47}{59}\big) \\ &= \big(\frac{59}{47}\big) \\ &= \big(\frac{12}{47}\big) \\ &= \big(\frac{3}{47}\big)\big(\frac{2}{47}\big)\big(\frac{2}{47}\big)\\ \end{align} As you can see we want the symbol to contain primes so that we can use Quadratic Reciprocity. From here we use the Fact [c.f. $\textit{A Course in Arithmetic}$. J.P. Serre. 1.3.1 Theorem 5]: $\big(\frac{2}{p}\big) = (-1)^{\frac{p^2 - 1}{2}\pmod 2}$ for p a prime, and then we have that $\big(\frac{3}{47}\big) = \big(\frac{47}{3}\big) = \big(\frac{2}{3}\big)$ and we use the same formula. I hope that clear things up.