Homework 4: Primitive Roots and
Quadratic Reciprocity
DUE WEDNESDAY, OCTOBER 17

William Stein

Date: Math 124 $\quad$ HARVARD UNIVERSITY $\quad$ Fall 2001

(1 point) Why do you think that quadratic reciprocity is so cool?

1.

(2 points) Calculate the following symbols by hand: $\left(\frac{3}{97}\right)$, $\left(\frac{5}{389}\right)$, $\left(\frac{2003}{11}\right)$, and $\left(\frac{5!}{7}\right)$.

2.

(3 points) Prove that $$\left(\frac{3}{p}\right) = \begin{cases}\hfill 1 & \text{ if }p\equiv 1, 11\pmod{12},\\ -1 & \text{ if }p\equiv 5, 7\pmod{12}. \end{cases}$$

3.

(3 points) Prove that there is no primitive root modulo $2^n$ for any $n\geq 3$.

4.

(6 points) Prove that if $p$ is a prime, then there is a primitive root modulo $p^2$.

5.

(5 points) Use the fact that $(\mathbb{Z}/p\mathbb{Z})^*$ is cyclic to give a direct proof that $\left(\frac{-3}{p}\right)=1$ when $p\equiv 1\pmod{3}$. [Hint: There is an $c\in (\mathbb{Z}/p\mathbb{Z})^*$ of order $3$. Show that $(2c+1)^2=-3$.]

6.

(6 points) If $p\equiv 1\pmod{5}$, show directly that $\left(\frac{5}{p}\right)=1$ by the method of Exercise 5. [Hint: Let $c\in (\mathbb{Z}/p\mathbb{Z})^*$ be an element of order $5$. Show that $(c+c^4)^2+(c+c^4)-1=0$, etc.]

7.

(4 points) For which primes $p$ is $$\sum_{a=1}^{p-1} \left(\frac{a}{p}\right)=0$$?

8.

(4 points) Artin conjectured that the number of primes $p\leq x$ such that $2$ is a primitive root modulo $p$ is asymptotic to $C\pi(x)$ where $\pi(x)$ is the number of primes $\leq x$ and $C$ is a fixed constant called Artin's constant. Using a computer, make an educated guess as to what $C$ should be, to a few decimal places of accuracy. Explain your reasoning. (Note: Don't try to prove that your guess is correct.)