Primes in arithmetic progressions having a prescribed primitive root

Pieter Moree

Abstract

Let g ∈ ℤ be not −1 or a square. Let P_{g} denote the set of primes p such that g is a primitive root mod p. Let f ≥ 1 and 1 ≤ a ≤ f, (a, f) = 1. Under the Generalized Riemann Hypothesis (GRH) it can be shown that the set of primes p ∈ P_{g} with p ≡ a(mod f), has a natural density. In this note this density is explicitly evaluated.

1 Introduction

Let g ∈ ℤ be not −1 or a square. Let P_{g} denote the set of primes p such that g is a primitve root mod p. It was conjectured by Emil Artin in 1927 that P_{g} is infinite. There is no integer g for which this has been proved, however, Heath-Brown [1] in a classical paper established a result which implies, for example, that there are at most two primes q for which P_{q} is finite. In 1967 Hooley [2] established Artin’s conjecture under the assumption of the Generalized Riemann Hypothesis (GRH). Moreover, he showed that under that assumption the set P_{g} has a natural density, which he evaluated (his result is Theorem 2 below with a = 1 and f = 1). It turns out that this density is a rational number times the Artin constant A, with

A = ∏_{p} (1 − \frac{1}{p(p − 1)}) ≈ .37395581.

In connection with his study of Euclidian number fields, Lenstra [3] considered the distribution over arithmetic progressions of the primes in P_{g}. Let P_{a,f,g} denote the set of primes such that g is a primitive root mod p and p ≡ a(mod f). From Lenstra’s work it follows that, under GRH, P_{a,f,g} has a natural density.

Theorem 1 [3]. Put ζ_{m} = e^{2πi/m}. Let f ≥ 1 and 1 ≤ a ≤ f, (a, f) = 1. Let σ_{a} be the automorphism of ℚ(ζ_{f}) determined by σ_{a}(ζ_{f}) = ζ_{f}^{a}. Let c_{a}(n) be 1 if the restriction of σ_{a} to the field ℚ(ζ_{f}) ∩ ℚ(ζ_{n}, g^{1/n}) is the identity and c_{a}(n) = 0 otherwise. Put

δ(a, f, g) = ∑_{n=1}^{∞} \frac{μ(n)c_{a}(n)}{[ℚ(ζ_{f}, ζ_{n}, g^{1/n}) : ℚ]}.

Then, assuming GRH, we have

π_{g}(x; f, a) = δ(a, f, g)\frac{x}{log x} + O (\frac{x log log x}{log^{2} x}) ,

where π_{g}(x; f, a) denotes the number of primes p ≤ x that are in P_{a,f,g}.

In the light of the apparent arithmetical complexity of Lenstra’s formula, the following relatively simple expression for δ(a, f, g) may come as a bit of a surprise.

Theorem 2 Let g ∈ ℤ be not −1 or a square. Let h ≥ 1 be the largest integer such that g is an hth power. Let Δ denote the discriminant of the quadratic field ℚ(\sqrt{g}). Let f ≥ 1 and 1 ≤ a ≤ f, (a, f) = 1. Let b = Δ/(f, Δ). Put

A(a, f, h) = ∏_{p|(a−1,f)}(1 − \frac{1}{p}) ∏_{{p∤f \atop p|h}}(1 − \frac{1}{p − 1}) ∏_{{p∤f \atop p∤h}} (1 − \frac{1}{p(p − 1)})

if (a − 1, f, h) = 1 and A(a, f, h) = 0 otherwise. Then

δ(a, f, g) = \frac{A(a, f, h)}{φ(f)} (1 + (\frac{Δ}{a})(\frac{a}{|b|})\frac{μ(2|b|)}{∏_{p|b, p|h}(p − 2) ∏_{p|b, p∤h}(p^{2} − p − 1)}) .

Here (Δ/a) denotes the Kronecker symbol and (a/|b|) the Jacobi symbol.

In case b is even, the Jacobi symbol (a/b) is not defined, then however μ(2b) = 0 and the term involving μ(2b) is taken to be zero. Write g = g_{1}g_{2}^{2}, with g_{1} squarefree. Then Δ = g_{1} if g_{1} ≡ 1(mod 4) and Δ = 4g_{1} otherwise. We see that b is odd if and only if g_{1} ≡ 1(mod 4) or g_{1} ≡ 2(mod 4) and 8|f or g_{1} ≡ 3(mod 4) and 4|f. Theorem 2 can be reformulated, using properties of the Kronecker symbol (see Section 2), in terms of g_{1}.

Theorem 3 Let a, f, g, h and A(a, f, h) be as in Theorem 2. Let g̃_{1} denote the odd part of g_{1}. Let β = g_{1}/(g_{1}, f). We have

δ(a, f.g) = \frac{A(a, f, h)}{φ(f)} (1 − (\frac{a}{(f, g_{1})})\frac{(−1)^{\frac{g̃_{1}−1}{2} \frac{a−1}{2}} μ(|β|)}{∏_{p|β, p|h}(p − 2) ∏_{p|β, p∤h}(p^{2} − p − 1)})

in case g_{1} ≡ 1(mod 4) or g_{1} ≡ 2(mod 4) and 8|f or g_{1} ≡ 3(mod 4) and 4|f and

δ(a, f, g) = \frac{A(a, f, h)}{φ(f)},

otherwise. Here (./.) denotes the Jacobi symbol with the stipulation that (a/2) = (−1)^{(a^{2}−1)/8}.

From Theorem 2 various known results can be rather easily deduced. That will be the subject of Section 5. The remaining sections are devoted to proving Theorem 2.

The author thanks F. Lemmermeyer and P. Stevenhagen for some helpful remarks.

2 Some facts from algebraic number theory

Although Theorem 1 suggests differently, the problem of evaluating δ(a, f, g) really only involves cyclotomic fields, quadratic subfields and their composita. In this section some facts concerning these fields relevant for the proof of Theorem 2 are discussed. We start by recalling some properties of the Kronecker symbol, a rarely covered topic in books on number theory.

The Kronecker symbol (c/d) is defined for c ∈ ℤ, c ≡ 0(mod 4) or c ≡ 1(mod 4), c not a square, and d ≥ 1 an integer; if b = p_{1}p_{2} ⋯ p_{s} is the decomposition of b as a product of primes, we put (a/−b) = (a/b) = (a/p_{1})(a/p_{2}) ⋯ (a/p_{s}). If p is an odd prime (a/p) = 0 when p divides a, while (a/p) is the Legendre symbol (a/p) when p does not divide a and, finally, (a/2) = 1 when a ≡ 1(mod 8), while (a/2) = −1 when a ≡ 5(mod 8). Then if a and b are such that both the Jacobi and the Kronecker symbols are defined, then these symbols coincide. If a is odd, then (a/2) = Jacobi symbol (2/|a|). If b > 0, (a, b) = 1, a is odd, then (a/b) = (b/|a|), with the Jacobi symbol in the right. Mosty importantly, if b > 0, (a, b) = 1 and a = 2^{r}ã with ã odd, then

(\frac{a}{b}) = (\frac{2}{b})^{r}(−1)^{\frac{ã−1}{2} \frac{b−1}{2}} (\frac{b}{|ã|}),  (1)

with Jacobi symbols in the right.

The following lemma allows one to determine all quadratic subfields of a given cyclotomic field (for a proof see e.g. [9, p. 163]).

Lemma 1 Let ℚ(\sqrt{d}) be a quadratic field of determinant Δ_{d}. Then the smallest cyclotomic field containing ℚ(\sqrt{d}) is ℚ(ζ_{|Δ_{d}|}).

Consider the cyclotomic field ℚ(ζ_{f}). There are φ(f) distinct automorphisms given by σ_{a}(ζ_{f}) = ζ_{f}^{a}, with 1 ≤ a ≤ f and (a, f) = 1. We need to know when the restriction of such an automorphism to a given quadratic subfield of ℚ(ζ_{f}) is the identity. In this direction we have

Lemma 2 Let ℚ(\sqrt{d}) ⊆ ℚ(ζ_{f}) be a quadratic field of determinant Δ_{d}. We have σ_{a}|_{ℚ(\sqrt{d})} =id if and only if (Δ_{d}/a) = 1, where (./.) denotes the Kronecker symbol.

Proof. Notice that, by Lemma 1, we can restrict to the case where f = |Δ_{d}|. Define χ by χ(a) = σ_{a}(\sqrt{d})/\sqrt{d}, 1 ≤ a ≤ |Δ_{d}|, (a, Δ_{d}) = 1. Then χ is the uniqe non-trivial character of the character group of ℚ(\sqrt{d}). As is well-known (see e.g. [7, p. 437]) the primitive character induced by this is (Δ_{d}/a). Using Lemma 1, we see that χ is a primitive character mod |Δ_{d}|. Thus χ(a) = (Δ_{d}/a). Now σ_{a}|_{ℚ(\sqrt{d})} =id if and only if χ(a) = (Δ_{d}/a) = 1. □

Remark. It is also possible to prove Lemma 2 using quadratic reciprocity and properties of Gauss sums.

The next result can be proved by a trivial generalization of an argument given by Hooley [2, pp. 213-214].

Lemma 3 Let g ∈ G and let h be the largest positive integer such that g is a pure hth power. Suppose that k|r and k is squarefree. Put k_{1} = k/(k, h) and n(k, r) = [ℚ(ζ_{r}, g^{1/k}) : ℚ]. Then i) if k is odd, n(k, r) = k_{1}φ(r);

ii) if k is even and Δ ∤ r, n(k, r) = k_{1}φ(r);

iii) if k is even and Δ|r, n(k, r) = k_{1}φ(r)/2.

The next lemma together with Lemma 2 allows one to compute c_{a}(n).

Lemma 4 Let g ∈ ℤ be not −1 or a square. Let Δ denote the discriminant of ℚ(\sqrt{g}). Let n ≥ 1 be squarefree and f ≥ 1 be arbitrary. Put b = Δ/(f, Δ). Then

ℚ(ζ_{f}) ∩ ℚ(ζ_{n}, g^{1/n}) = ℚ(ζ_{(f,n)}, \sqrt{(−1)^{(b−1)/2}(f, Δ)})

if n is even, Δ ∤ n and Δ|lcm(f, n) and

ℚ(ζ_{f}) ∩ ℚ(ζ_{n}, g^{1/n}) = ℚ(ζ_{(f,n)})

otherwise.

Proof. On noting that φ((f, n))φ(lcm(f, n)) = φ(f)φ(n), it easily follows, using Lemma 3, that

[ℚ(ζ_{f}) ∩ ℚ(ζ_{n}, g^{1/n}) : ℚ(ζ_{(f,n)})] = 2  (2)

if n is even, Δ ∤ n and Δ|lcm(f, n) and ℚ(ζ_{f}) ∩ ℚ(ζ_{n}, g^{1/n}) = ℚ(ζ_{(f,n)}) otherwise. Thus we may assume that n is even, Δ ∤ n and Δ|lcm(f, n). Notice that this implies that b is odd. Put γ = (−1)^{(b−1)/2}(f, Δ). We now distinguish cases according to the residue mod 4 of the odd part of Δ, respectively the odd part of (f, Δ). In each case we check, using Lemma 1, that \sqrt{γ} ∉ ℚ(ζ_{(f,n)}), \sqrt{γ} ∈ ℚ(ζ_{f}) and \sqrt{Δ/γ} ∈ ℚ(ζ_{n}). These inclusion relations together with (2) yield the result.

3 Euler products

In this section we prove some results that will help us to write down the Euler product of the sums encountered in the proof of the main result (Theorem 2).

Proposition 1 Let f, h ≥ 1 be integers. Then the function w : ℕ → ℕ defined by

w(k) = \frac{kφ(lcm(k, f))}{(k, h)φ(f)}

is multiplicative. Furthermore,

i) if p ∤ h and p ∤ f, then w(p) = p(p − 1)

ii) if p ∤ h and p|f, then w(p) = p

iii) if p|h and p ∤ f, then w(p) = p − 1

iv) if p|h and p|f, then w(p) = 1

v) if h is odd, then w(2) = 2.

This will help us to prove the following lemma.

Lemma 5 Let f, h ≥ 1 be integers with 1 ≤ a ≤ f, (a, f) = 1 and h odd. Let Δ be a discriminant of a quadratic number field. Let b = Δ/(f, Δ). Put

S(b) = ∑_{{n=1, Δ|lcm(n,f) \atop a≡1(mod (f,n))}}^{∞} \frac{μ(n)}{w(n)}.

Let S_{2}(b) denote the same sum as S(b) but with the restriction that 2|n. Then S(b) = 0 if b is even and

S(b) = \frac{μ(b)A(a, f, h)}{∏_{p|b}(w(p) − 1)}

otherwise. Furthermore, S_{2}(b) = −S(b).

Proof. If b is even, then the summation in S(b) runs over non squarefree n only and hence S(b) = 0. Next assume that b is odd. We have

S(b) = ∑_{{n=1, b|n/(f,n) \atop a≡1(mod (f,n))}}^{∞} \frac{μ(n)}{w(n)} = ∑_{d|(a−1,f)} ∑_{{n=1, (f,n)=d \atop b|n/d}}^{∞} \frac{μ(n)}{w(n)}

= ∑_{d|(a−1,f)} \frac{μ(d)}{w(d)} ∑_{{n=1, (f,n)=1 \atop b|n}}^{∞} \frac{μ(n)}{w(n)} = \frac{μ(|b|)}{w(|b|)} ∑_{d|(a−1,f)} \frac{μ(d)}{w(d)} ∑_{{n=1, (f,nb)=1 \atop (b,n)=1}}^{∞} \frac{μ(n)}{w(n)}.

Now by assumption Δ is a discriminant and b is odd. This implies that (f, b) = 1 and b is squarefree. Thus

S(b) = \frac{μ(|b|)}{w(|b|)} ∏_{p|(a−1,f)}(1 − \frac{1}{w(p)}) ∏_{p∤fb}(1 − \frac{1}{w(p)})

= \frac{μ(|b|)}{w(|b|)} ∏_{p|(a−1,f)}(1 − \frac{1}{w(p)}) ∏_{p∤f}(1 − \frac{1}{w(p)}) ∏_{p|b}(1 − \frac{1}{w(p)})^{−1}

= \frac{μ(|b|)A(a, f, h)}{∏_{p|b}(w(p) − 1)},

where we used that w(p) > 1 for p|b and

∏_{p|(a−1,f)}(1 − \frac{1}{w(p)}) ∏_{p∤f}(1 − \frac{1}{w(p)}) = A(a, f, h),

an identity immediately obtained on invoking Proposition 1.

The latter part of the assertion follows easily on using that w(2) = 2. □

4 Proof of the main result

Proof of Theorem 2. Let γ be as in the proof of Lemma 4. Suppose that b is odd. Note that the disriminant of ℚ(\sqrt{γ}) equals γ. On using (1), it is seen that the Kronecker symbol (γ/a) equals (Δ/a)(a/|b|).

i) The case b is odd and (Δ/a)(a/|b|) = 1. Using Lemma 4, Lemma 2 and the observation above, we find that c_{a}(n) = 1 in case a ≡ 1(mod (f, n)) and c_{a}(n) = 0 otherwise. This together with Theorem 1 and Lemma 3 implies that

φ(f)δ(a, f, g) = ∑_{{n=1 \atop 2∤n}}^{∞} \frac{μ(n)}{w(n)} + ∑_{{n=1, 2|n \atop Δ∤lcm(n,f)}}^{∞} \frac{μ(n)}{w(n)} + 2 ∑_{{n=1, 2|n \atop Δ|lcm(n,f)}}^{∞} \frac{μ(n)}{w(n)}.

= ∑_{n=1}^{∞} \frac{μ(n)}{w(n)} + ∑_{{n=1, 2|n \atop Δ|lcm(n,f)}}^{∞} \frac{μ(n)}{w(n)} = I_{1} + S_{2}(b),  (3)

where furthermore in each sum we restrict to those integers n such that a ≡ 1(mod (f, n)). Now, on using Proposition 1,

I_{1} = ∑_{d|(a−1,f)} ∑_{(f,n)=d} \frac{μ(n)}{w(n)} = ∑_{d|(a−1,f)} \frac{μ(d)}{w(d)} ∑_{(f,n)=1} \frac{μ(n)}{w(n)}
= ∏_{p|(a−1,f)}(1 − \frac{1}{w(p)}) ∏_{p∤f}(1 − \frac{1}{w(p)}) = A(a, f, h).

The result follows from (3) on invoking Lemma 5 and Proposition 1.

ii) The case b is odd and (Δ/a)(a/|b|) = −1. Using Lemma 4, Lemma 2, the observation in the beginning of this proof and (3), we find

φ(f)δ(a, f, g) = I_{1} + S_{2}(b) − 2 ∑_{{2|n, Δ∤n \atop Δ|lcm(f,n)} a≡1(mod (f,n))} \frac{μ(n)}{w(n)}.

Now

∑_{{2|n, Δ|lcm(f,n) \atop a≡1(mod (f,n))}} \frac{μ(n)}{w(n)} = ∑_{{2|n, Δ∤n \atop Δ|lcm(f,n)} a≡1(mod (f,n))} \frac{μ(n)}{w(n)} + ∑_{{2|n, Δ|n \atop a≡1(mod (f,n))}} \frac{μ(n)}{w(n)}.

In case Δ ≡ 0(mod 4), the latter sum is obviously zero. In case Δ ≡ 1(mod 4), a necessary condition for the latter sum to be non-zero is that a ≡ 1(mod (f, 2Δ)). For such a, we have however, (Δ/a)(a/b) = (a/(f, Δ)) = 1. It thus follows that φ(f)δ(a, f, g) = I_{1} − S_{2}(b).

iii) The case b is even. As in the case where b is odd, we either have that φ(f)δ(a, f, g) = I_{1} + S_{2}(b) or φ(f)δ(a, f, g) = I_{1} − S_{2}(b). By Lemma 5 it then follows that φ(f)δ(a, f, g) = I_{1}. □

5 Applications

Setting a = 1 and f = 1 in Theorem 2 we obtain Hooley’s theorem [2]. Setting a = 1 we obtain Theorem 4 of [5]. Notice that of all the progressions mod f, the progression 1(mod f) is the easiest to deal with, since trivially c_{1}(n) = 1 for every n.

Rodier [8], in connection with a coding theoretical problem, conjectured that the density of the primes in P_{2} such that p ≡ −1, 3 or 19(mod 28) is A/4. From Theorem 2 it follows however that, under GRH, this density is 21A/82 (cf. [4]).

Lenstra [3, Theorem 8.3] gave a sketch of a proof of the following result.

Theorem 4 Let g ∈ ℤ be not −1 or a square and h be the largest integer such that g is an hth power. Then δ(a, f, g) = 0 if and only if one of the following holds

i) (a − 1, f, h) > 1;

ii) Δ|f and (\frac{Δ}{a}) = 1 (Kronecker symbol);

iii) Δ|3f, 3|Δ, 3|h and (\frac{−Δ/3}{a}) = −1.

This result very easily follows from Theorem 2. We leave it to the reader to show that if δ(a, f, g) = 0, then actually P_{g} is finite.

If S is any set of integers, denote by S(x) the number of integers in S not exceeding x. For given integers a and f, denote by S(x; f, a) the number of integers in S not exceeding x that are congruent to a modulo f. We say that S is weakly uniformly distributed mod f (or WUD mod f for short) if S(x) → ∞ (x → ∞) and for every a coprime to f,

S(x; f, a) ∼ \frac{S(x)}{φ(d)},

where φ(d) denotes Euler’s totient. The progressions a(mod f) such that the latter asymptotic equivalence holds and S(x) → ∞ (x → ∞) are said to get their fair share of primes from S. Thus S is weakly uniformly distributed mod f if and only if all the progressions mod f get their fair share of primes from S. Narkiewicz [6] has written a nice survey on the state of knowledge regarding the (weak) uniform distribution of many important arithmetical sequences. Let D_{g} denote the set of natural numbers f such that P_{g} is weakly uniformly distributed modulo f.

Theorem 5 (GRH). Let g ∈ ℤ be not −1 or a square and let h the largest integer such that g is a pure hth power. Write g = g_{1}g_{2}^{2} with g_{1} squarefree. Assume that not both g_{1} = 21 and (h, 21) = 7, then D_{g}, the set of natural numbers f such that the set of primes p such that g is a primitive root mod p is weakly uniformly distributed mod d, equals

i) {2^{n} : n ≥ 0} if g_{1} ≡ 1(mod 4);

ii) {1, 2, 4} if g_{1} ≡ 2(mod 4); iii) {1, 2} if g_{1} ≡ 3(mod 4).

In the remaining case g_{1} = 21 and (h, 21) = 7, we have D_{g} = {2^{n}3^{m} : n, m ≥ 0}.

Using only a formula for δ(1, f, g) and Theorem 1 in some special cases, this result was first deduced in [5]. Here a shorter proof, using the full force of Theorem 3, is given.

Proof of Theorem 5. Put S_{f} := {A(a, f, h) | 1 ≤ a ≤ f, (a, f) = 1}. Put

χ_{g,f}(a) = (−1)^{\frac{g̃_{1}−1}{2} \frac{a−1}{2}} (\frac{a}{(f, g_{1})}).

Let us first consider the case where f = 2^{m} for some m ≥ 0. In case g_{1} ≡ 1(mod 4), χ_{g,2^{m}} equals the identity, in case g_{1} ≡ 2(mod 4) and m ≥ 3, χ_{g,2^{m}} is not equal to the identity and similarly for g_{1} ≡ 3(mod 4) and m ≥ 2. Notice that |S_{2^{m}}| = 1. It follows that if g_{1} ≡ 1(mod 4) and m ≥ 0, then P_{g} is WUD mod 2^{m}. Similarly if g_{1} ≡ 2(mod 4) and m ≤ 2, or g_{1} ≡ 3(mod 4) and m ≤ 1. For the other pairs (g, 2^{m}), the image of δ(., f, g) has cardinality two and so P_{g} is not WUD mod 2^{m}.

It remains to deal with the case where f is odd. First let us consider the case where f = q with q an odd prime. In case β is even,

φ(f)δ(1, f, g) = A(1, f, h) ≠ A(2, f, h) = δ(2, f, g)φ(f)

and we do not have equidistribution. Next assume that β is odd. If q = 3, then a short calculation shows that a necessary and sufficient condition for equidistribution to occur, is that 3|g_{1}, (3, h) = 1, μ(|β|) = −1, g_{1} ≡ 1(mod 4) and the equation ∏_{p|β, p|h}(p−2) ∏_{p|β, p∤h}(p^{2} −p−1) = 5 has a solution with β is odd. Now notice that g is solution to this if and only if g_{1} = 21 and (h, 21) = 7. Call such a g exceptional. If q ≥ 5, then A(2, f, g) = A(3, f, g) = ⋯ = A(q − 1, f, g) and there exist 2 ≤ a_{1} < a_{2} ≤ q − 1 with (a_{1}/q) = −(a_{2}/q). Then δ(a_{1}, f, g) ≠ δ(a_{2}, f, g). From this it immediately follows that for odd f and g not exceptional, equidistribution does not occur, for if P_{g} is WUD mod f, then P_{g} must also be WUD mod δ for every divisor δ of f. It remains to show that when g is exceptional we have that P_{g} is WUD mod 2^{m}3^{n}, with m ≥ 0 and n ≥ 1 arbitrary. This follows easily from Theorem 2 and the calculation done in the case f = 3. □

References

[1] D.R. Heath-Brown, Artin’s conjecture for primitive roots, Quart. J. Math. Oxford 37 (1986), 27-38.

[2] C. Hooley, Artin’s conjecture for primitive roots, J. Reine Angew. Math. 225 (1967), 209-220.

[3] H. W. Lenstra, jr., On Artin’s conjecture and Euclid’s algorithm in global fields, Invent. Math. 42 (1977), 201-224.

[4] P. Moree, On a conjecture of Rodier on primitive roots, Abh. Math. Sem. Univ. Hamburg 67 (1997), 165-171.

[5] P. Moree, Uniform distribution of primes having a rational prescribed primitive root, MPI-preprint 23, 1998.

[6] W. Narkiewicz, Uniform distribution of sequences of integers in residue classes, Lecture Notes in Math. 1087, Springer, 1984.

[7] W. Narkiewicz, Elementary and analytic theory of algebraic numbers, Springer, 2nd edition, 1989.

[8] F. Rodier, Estimation asymptotique de la distance minimale du dual des codes BCH et polynômes de Dickson, Discrete Math. 149 (1996), 205-221.

[9] E. Weiss, Algebraic number theory, New York University Press, New York, 1963.

Max-Planck-Institut für Mathematik, Gottfried-Claren-Straße 26, 53225 Bonn, Germany.

(e-mail: moree@mpim-bonn.mpg.de)