Question

prove that 3 is a quadratic residue modulo 13 but a quadratic nonresidue modulo 7

Answer 1

Answer:

Let p=2q−1 where q must be prime for p to be Mersenne prime.

If q=2, p=22−1=3

So, we can start with odd q>2

⟹p−12=2q−22=2q−1−1 which is odd if q−1≥1

(3p)(p3)=(−1)(3−1)(p−1)4=−1

As q is odd q=2r+1(say)

2q=2⋅22r=2⋅4r≡2(mod3) as (4−1)∣(4r−1)

⟹p=2q−1≡1(mod3)

⟹(p3)=(13)=1

⟹(3p)=−1