# The Legendre Symbol

Prove

$latex x^{2} \equiv 3411 \mod 3457$
has no solution?

Legendre Symbol:

$latex \displaystyle x^{2} \equiv a \mod p \iff \boxed{ \left( \frac {a}{p} \right) = \begin{cases} -1, & \text{if 0 solution} \\ 0 , & \text{if 1 solution} \\ 1, & \text{if 2 solutions} \\ \end{cases} }$

Hint: prove $latex \left( \frac{3411}{3457} \right) = -1$

Using the Law of Quadratic Reciprocity, without computations, we can prove there is no solution for this equation.

Solution:

1.
3411 = 3 x 3 x 379 = 9 x 379

$Latex \displaystyle \boxed{ \left(\frac{a}{p}\right) \left(\frac{b}{p} \right)= \left(\frac{ab}{p}\right) }$

$latex \displaystyle \left(\frac{3411}{3457} \right)= \left(\frac{9}{3457} \right).\left(\frac{379}{3457} \right)= \left(\frac{379}{3457} \right)$
since
$latex \displaystyle\left(\frac{9}{3457} \right)=1$
because 9 is a perfect square, 3457 is prime.

$latex \displaystyle \boxed{ \text{If p or q or both are } \equiv 1 \mod 4 \implies \left(\frac{p}{q} \right)= \left(\frac{q}{p} \right)}$