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.

2. By Quadratic Reciprocity,
$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)}
$

Since
$latex…