Let's play with Legendre's symbol!

Is 402 402 a quadratic residue m o d 991 \bmod991 ?

Hint: 991 991 is a prime.

No Yes Cannot be determined

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Mark Hennings
Aug 30, 2018

We start with ( 402 991 ) = ( 2 991 ) ( 3 991 ) ( 67 991 ) \left(\frac{402}{991}\right) \; = \; \left(\frac{2}{991}\right) \left(\frac{3}{991}\right)\left(\frac{67}{991}\right) Now 991 1 ( m o d 8 ) 991 \equiv -1 \pmod{8} , and so ( 2 991 ) = 1 \left(\frac{2}{991}\right) = 1 . Also 1 4 ( 3 1 ) ( 991 1 ) \tfrac14(3-1)(991-1) and 1 4 ( 67 1 ) ( 991 1 ) \tfrac14(67-1)(991-1) are both odd, and hence ( 402 991 ) = ( 991 3 ) × ( 991 67 ) = ( 1 3 ) ( 53 67 ) = ( 53 67 ) \left(\frac{402}{991}\right) \; = \; -\left(\frac{991}{3}\right) \times -\left(\frac{991}{67}\right) \; = \; \left(\frac{1}{3}\right) \left(\frac{53}{67}\right) \; = \; \left(\frac{53}{67}\right) Now 1 4 ( 53 1 ) ( 67 1 ) \tfrac14(53-1)(67-1) is even, and hence ( 402 991 ) = ( 67 53 ) = ( 14 53 ) = ( 2 53 ) ( 7 53 ) \left(\frac{402}{991}\right) \; = \; \left(\frac{67}{53}\right) \; = \; \left(\frac{14}{53}\right) \; = \; \left(\frac{2}{53}\right) \left(\frac{7}{53}\right) Now 53 5 ( m o d 8 ) 53 \equiv 5 \pmod{8} and 1 4 ( 7 1 ) ( 53 1 ) \tfrac14(7-1)(53-1) is even, and so ( 402 991 ) = ( 53 7 ) = ( 4 7 ) = 1 \left(\frac{402}{991}\right) \; = \; -\left(\frac{53}{7}\right) \; = \; -\left(\frac{4}{7}\right) \; = \; -1 which means that 402 402 is not a quadratic residue modulo 991 991 .

Jesse Nieminen
Sep 1, 2018

gcd ( 402 , 991 ) = 1 \gcd(402, 991) = 1 meaning that Jacobi Symbol ( 402 991 ) \left(\dfrac{402}{991}\right) must be 1 1 if 402 402 is a quadratic residue modulo 991 991 .

However by the properties of Jacobi Symbol,

( 402 991 ) = ( 201 991 ) = ( 187 201 ) = ( 14 187 ) = ( 7 187 ) = ( 5 7 ) = ( 2 5 ) = 1 \left(\dfrac{402}{991}\right) = \left(\dfrac{201}{991}\right) = \left(\dfrac{187}{201}\right) = \left(\dfrac{14}{187}\right) = - \left(\dfrac{7}{187}\right) = \left(\dfrac{5}{7}\right) = \left(\dfrac{2}{5}\right) = -1

Hence, N o \boxed{\mathrm{No}}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...