Homework 4: Primitive Roots and Quadratic Reciprocity

Due Wednesday, October 17

William Stein

Math 124 Harvard University Fall 2001

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

2. (3 points) Prove that (\frac{3}{p}) = \begin{cases}1 & if p ≡ 1, 11 (mod 12), \\ −1 & if p ≡ 5, 7 (mod 12). \end{cases}

3. (3 points) Prove that there is no primitive root modulo 2^{n} for any n ≥ 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 (ℤ/pℤ)^{∗} is cyclic to give a direct proof that (\frac{−3}{p}) = 1 when p ≡ 1 (mod 3). [Hint: There is an c ∈ (ℤ/pℤ)^{∗} of order 3. Show that (2c + 1)^{2} = −3.]

6. (6 points) If p ≡ 1 (mod 5), show directly that (\frac{5}{p}) = 1 by the method of Exercise 5. [Hint: Let c ∈ (ℤ/pℤ)^{∗} 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 ∑_{a=1}^{p−1} (\frac{a}{p}) = 0?

8. (4 points) Artin conjectured that the number of primes p ≤ x such that 2 is a primitive root modulo p is asymptotic to Cπ(x) where π(x) is the number of primes ≤ 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.)