Exercise (7.3).10

Determine the following Legendre symbols by using Gauss’s Lemma:

(a) $(\frac{3}{13})$

(b) $(\frac{3}{17})$

(c) $(\frac{3}{19})$

(d) $(\frac{3}{23})$

(a) The following table shows the calculation of $3n \pmod {13}$ for $1 \le n \le \frac{13-1}{2}$, which values larger than $\frac{13-1}{2}$ shown as the smallest negative residues. 

n	3n mod 13	3n mod 13
1	3	3
2	6	6
3	9	-4
4	12	-1
5	2	2
6	5	5

There are 2 negative such residues. By Gauss' Lemma

$$ (\frac{3}{13}) = (-1)^2 = 1$$

And so by Euler's Criterion 3 is a quadratic residue of odd prime 13.

(b) The following table shows the calculation of $3n \pmod {13}$ for $1 \le n \le \frac{17-1}{2}$, which values larger than $\frac{17-1}{2}$ shown as the smallest negative residues. 

n	3n mod 17	3n mod 17
1	3	3
2	6	6
3	9	-8
4	12	-5
5	15	-2
6	1	1
7	4	4
8	7	7

There are 3 negative such residues. By Gauss' Lemma

$$ (\frac{3}{17}) = (-1)^3 = -1$$

And so by Euler's Criterion 3 is a quadratic non-residue of odd prime 17.

(c) The following table shows the calculation of $3n \pmod {19}$ for $1 \le n \le \frac{19-1}{2}$, which values larger than $\frac{19-1}{2}$ shown as the smallest negative residues. 

n	3n mod 19	3n mod 19
1	3	3
2	6	6
3	9	9
4	12	-7
5	15	-4
6	18	-1
7	2	2
8	5	5
9	8	8

There are 3 negative such residues. By Gauss' Lemma

$$ (\frac{3}{19}) = (-1)^3 = -1$$

And so by Euler's Criterion 3 is a quadratic non-residue of odd prime 19.

(d) The following table shows the calculation of $3n \pmod {23}$ for $1 \le n \le \frac{23-1}{2}$, which values larger than $\frac{23-1}{2}$ shown as the smallest negative residues. 

n	3n mod 23	3n mod 23
1	3	3
2	6	6
3	9	9
4	12	-11
5	15	-8
6	18	-5
7	21	-2
8	1	1
9	4	4
10	7	7
11	10	10

There are 4 negative such residues. By Gauss' Lemma

$$ (\frac{3}{23}) = (-1)^4 = 1$$

And so by Euler's Criterion 3 is a quadratic residue of odd prime 23.