Evaluate the following Legendre symbols using quadratic reciprocity:

  1. $\left(\frac{295}{401}\right)$
  2. $\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.

  • 2
    $\begingroup$ Or even easier: $\big(\frac{12}{47}\big) = \big(\frac{3}{47}\big)\big(\frac{4}{47}\big) = \big(\frac{3}{47}\big)$. $\endgroup$ – rogerl May 5 '15 at 1:11
  • $\begingroup$ Thanks so much to you both! My problem was that I didn't initially change the top number into its prime factorization and that's why the numbers were coming out strange. $\endgroup$ – elenor May 5 '15 at 1:28

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.