Quadratic Residues

note

This is Lab 15 from Clint by Hugh Montgomery, edited by Elad Zelingher. All rights reserved to Hugh Montgomery.

As is discussed at the end of $\S 3.3$ of NZM, quadratic reciprocity provides a quick method of calculating the Jacobi symbol. The program JacobDem demonstrates the process. In addition, values of the Jacobi symbol exhibit a number of interesting and important patterns. These we can explore with the aid of the program JacobTab.

Problem 1

Use the program JacobDem to witness the calculation of the Jacobi symbol. Use JacobDem to compute $\left(\frac{1234567}{7654321}\right)$. To evaluate the Jacobi symbol without witnessing the calculation, use the program Jacobi.

Problem 2

Use the program JacobTab to view a table of the values of the Jacobi symbol. For $p=23$, what are the quadratic residues?

Problem 3

For $1 \leq a \leq p-2$, the pair $\left(\frac{a}{p}\right),\left(\frac{a+1}{p}\right)$ takes on the values $(1,1),(1,-1),(-1,1)$, $(-1,-1)$. Using JacobTab with $p=29$, classify the $a$ according to which pair is generated. How many times does each configuration occur? Repeat this with $p=37, p=41$. Formulate a conjecture concerning the general situation when $p \equiv 1(\bmod 4)$. Now try some primes $\equiv 3 (\bmod 4)$, say $p=23, p=31, p=43$. Again, formulate a conjecture. Problem 18 at the end of $\S 3.3$ of NZM is relevant here.

Problem 4

Using JacobTab, evaluate the sum

$$\sum_{a=1}^{p}\left(\frac{a(a+1)}{p}\right)$$

for several primes, say $p=11, p=13, p=17, p=19$. Formulate a conjecture concerning the value of this sum. Note Problem 17 at the end of $\S 3.3$ of NZM.

Problem 5

Let $\delta= \pm 1, \epsilon= \pm 1$. The $a$ for which $\left(\frac{a}{p}\right)=\delta,\left(\frac{a+1}{p}\right)=\epsilon$ are counted by the expression

$$\frac{1}{4} \sum_{a=1}^{p-2}\left(1+\delta\left(\frac{a}{p}\right)\right)\left(1+\epsilon\left(\frac{a+1}{p}\right)\right)$$

Explain why this is

$$=-\frac{1}{4}\left(1+\epsilon\left(\frac{-1}{p}\right)\right)-\frac{1}{4}(1+\delta)+\frac{1}{4} \sum_{a=1}^{p}\left(1+\delta\left(\frac{a}{p}\right)\right)\left(1+\epsilon\left(\frac{a+1}{p}\right)\right)$$

and why this in turn is

$$=\frac{1}{4}\left(p-2-\delta-\epsilon\left(\frac{-1}{p}\right)\right)+\frac{\delta \epsilon}{4} \sum_{a=1}^{p}\left(\frac{a(a+1)}{p}\right) .$$

This identity establishes a relationship between the conjectures you made in the two preceding problems. Are your conjectures equivalent?

Problem 6

Using JacobTab, evaluate the sum

$$\sum_{a=1}^{(p-1) / 2}\left(\frac{a}{p}\right)$$

for several odd prime numbers $p$, say $p=11, p=13, p=17, p=19$. Explain why this sum must vanish if $p \equiv 1(\bmod 4)$. (Hint: $\left(\frac{a}{p}\right)=\left(\frac{-a}{p}\right)$.) Explain why this sum never vanishes if $p \equiv 3(\bmod 4)$. (Hint: What is this sum $(\bmod 2)$ ?) When $p \equiv 3(\bmod 4)$, is there anything notable about the sign of this sum? Examine some further cases, and formulate a conjecture.

In 1839 , Dirichlet proved an important class number formula, a special case of which asserts that if $p \equiv 3(\bmod 4)$ and $p>3$ then

$$\sum_{a=1}^{(p-1) / 2}\left(\frac{a}{p}\right)=\left(2-\left(\frac{2}{p}\right)\right) H(-p)$$

Here $H(-p)$ is the number of inequivalent classes of quadratic forms of discriminant $-p$, as defined in $\S 3.5$ of NZM. From this (deep) result we see that the sum on the left hand side above is always positive when $p \equiv 3(\bmod 4)$. For an exposition of Dirichlet's class number formula, see $\S 1$ and $\S 9$ of H. Davenport, Multiplicative Number Theory, 2nd Edition, Springer-Verlag, New York, 1980, especially (8) on p. 9 and (15) on p. 49.

Problem 7

Using JacobTab as an aid, test the following assertion: For every prime number $p \geq 11$, the interval $[1,10]$ contains two consecutive quadratic residues. Is the same true of the interval $[1,9]$ ? Is there a similarly uniform upper bound for the first occurrence of three consecutive quadratic residues? Explore. The answer, which will come as a surprise, is given by D. H. Lehmer and E. Lehmer, On runs of residues, Proc. Amer. Math. Soc. 13 (1962), 102-106.

Problem 8

Let $n_{2}(p)$ denote the least positive quadratic nonresidue of $p$. Using JacobTab, determine the value of $n_{2}(p)$ for 25 odd primes chosen at random. What values does $n_{2}(p)$ take on, and how many times? Is there any reason why the number $n_{2}(p)$ should always be prime?

Erdős combined quadratic reciprocity and the prime number theorem for arithmetic progressions to show that $n_{2}(p)=2$ for asymptotically $1 / 2$ of the primes, that $n_{2}(p)=3$ for asymptotically $1 / 4$ of the primes, that $n_{2}(p)=5$ for asymptotically $1 / 8$ of the primes, that $n_{2}(p)=7$ for asymptotically $1 / 16$ of the primes, and so on.

Problem 9

Let $p_{2}(p)$ denote the least prime quadratic residue of $p$. Using JacobTab, determine the value of $p_{2}(p)$ for 25 randomly chosen odd primes $p$. What values are taken on, and how frequently? What is $p_{2}(163)$ ?