# The Legendre Symbol

Prove

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

Legendre Symbol:

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

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

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

$\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
$3457 \equiv 1 \mod 4$
$\displaystyle \left(\frac{379}{3457}\right)= \left(\frac{3457}{379} \right)$

3.

$3457 \equiv 46 \mod 379$
46 = 2 × 23
$\displaystyle \left(\frac{3457}{379}\right)= \left(\frac{2}{379}\right). \left(\frac{23}{379}\right)$

4.
$\displaystyle \boxed{ \left( \frac {2}{p} \right) = \begin{cases} 1, & \text{if } p \equiv 1 \text{ or } \equiv 7 \mod 8\\ -1, & \text{if } p \equiv 3 \text { or } \equiv 5\mod 8\\ \end{cases} }$

$\displaystyle\left(\frac{2}{379} \right)=-1$
because
$379 \equiv 3 \mod 8$

$\displaystyle \left(\frac{3457}{379}\right)= - \left(\frac{23}{379}\right)$

5.
$\displaystyle \boxed{ \text{If p } \equiv q \equiv 3 \mod 4 \implies \left(\frac{p}{q} \right)= - \left(\frac{q}{p} \right)}$
Since
$23 \equiv 3 \mod 4$
and
$379 \equiv 3 \mod 4$

$\displaystyle - \left(\frac{23}{379} \right) = \left(\frac{379}{23} \right)$
$379 \equiv 11 \mod 23$

$\displaystyle \left(\frac{379}{23} \right) = \left(\frac{11}{23} \right)$

Similarly, as above,

$11 \equiv 3 \mod 4$

$\displaystyle \left(\frac{11}{23} \right) = -\left(\frac{23}{11} \right)$

$\displaystyle 23 \equiv 1 \mod 11$

$\displaystyle \left(\frac{11}{23}\right)= -\left(\frac{1}{11} \right) = -1$

Hence,
$\displaystyle \boxed{ \left(\frac{3411}{3457}\right) = -1}$
$\implies x^{2} \equiv 3411 \mod 3457$
has no solution.

[Reference]: