The Legendre Symbol

Math Online Tom Circle


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

Legendre Symbol:

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

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.


3411 = 3 x 3 x 379 = 9 x 379

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

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

2. By Quadratic Reciprocity,
$latex \displaystyle
\text{If p or q or both are } \equiv 1 \mod 4 \implies
\left(\frac{p}{q} \right)=
\left(\frac{q}{p} \right)}


View original post 212 more words

Author: mathtuition88

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.