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.

2. By Quadratic Reciprocity,
\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.
By Quadratic Reciprocity,
\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]:

Fearless Symmetry: Exposing the Hidden Patterns of Numbers (New Edition)

Advertisements

One thought on “The Legendre Symbol

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s