Number Theory Question 13 Solutionp 2 has a solution as 12

**Number Theory Question**

Solution

p = 2 has a solution as 1^2 13(mod 2) and p = 13 has a solution given by x = 0(mod 13). From now on we will look for odd primes p, different from 13 such that x ^2 13(mod p) has a solution. We are looking for odd primes p, different from 13 such that (13/p) = 1. As 13 1(mod 4), by quadratic reciprocity, (13/p) = 1 if and only if (p/13) = 1. (p /13) = p^ 6 (mod 13). Looking at residue classes of p modulo 13, we see that p^6 1(mod 13) if and only if p 1, 3, 4, 9, 10, 11(mod 13). (It is enough to test for p 1, 2, 3, 4, 5, 6(mod 13) as r^6 (r)^6 (mod 13) which implies primes congruent to r modulo 13 satisfy 13 | p^6 1 if and only if primes congruent to 13 r modulo 13 satisfy 13 | p^6 1). x^2 13(mod p) has a solution if and only if p = 2 or p = 13 or p 1, 3, 4, 9, 10, 11(mod 13).