7 Let n 5 For which primes p is 5 a quadratic residue mod p

7. Let n = 5. For which primes p is 5 a quadratic residue mod p? That is, for which primes p is (5/p) = 1? You do not need to give a proof of this, just a statement of the pattern you see by testing small primes.

Solution

For p=2

0²=0, 1²=1...5 is quadratic non residue mod 2

p=3

0²=0, 1²=1, 2²=1....5 is quadratic non residue mod 3

p=5

0²=0, 1²=1, 2²=4, 3²=4, 4²=1...5 is quadratic non residue mod 5

p=7

0²=0, 1²=1, 2²=4, 3²=2, 4²=2, 5²=4, 6²=1...5 is quadratic non residue mod 7

p=11

0²=0, 1²=1, 2²=4, 3²=9, 4²=5=> 5 is quadratic residue mod 11

p=13

0²=0, 1²=1, 2²=4, 3²=9, 4²=3, 5²=12, 4²=3, 5²=12, 6²=10, 7²=1, 8²=12, 9²=3, 10²=9, 11²=4, 12²=1...5 is quadratic non residue mod 13

p=17

0²=0, 1²=1, 2²=4, 3²=9, 4²=16, 5²= 8, 6²=2, 7²=15, 8²=13, 9²=13, 10²=15, 11²=2, 12²=8, 13²=16, 14²=9, 15²=4, 16²=1...5 is quadratic non residue mod 17

p=19

0²=0, 1²=1, 2²=4, 3²=9, 4²=16, 5²=6, 6²=17, 7²=11, 8²=7, 9²=15, 10²=5=> 5 is quadratic residue mod 19

From the above pattern we see that (5/11) =1, (5/19) =1

And so the primes are 11,19,....

These are of the the form 3 mod(4)

Therefore p = 3mod(4) so that (5/p)=1

In other words p is of the form 4j+3 so that 5 is quadratic residue mod p