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…

View original post 212 more words