On primes p for which d divides ord_{p}(g)

Pieter Moree

Abstract

Let N_{g}(d) be the set of primes p such that the order of g modulo p, ord_{p}(g), is divisible by a prescribed integer d. Wiertelak showed that this set has a natural density, δ_{g}(d), with δ_{g}(d) ∈ ℚ_{>0}. Let N_{g}(d)(x) be the number of primes p ≤ x that are in N_{g}(d). A simple identity for N_{g}(d)(x) is established. It is used to derive a more compact expression for δ_{g}(d) than known hitherto.

1 Introduction

Let g be a rational number such that g ∉ {−1, 0, 1} (this assumption on g will be maintained throughout this note). Let N_{g}(d) denote the set of primes p such that the order of g(mod p) is divisible by d (throughout the letter p will also be used to indicate primes). Let N_{g}(d)(x) denote the number of primes in N_{g}(d) not exceeding x. The quantity N_{g}(d)(x) (and some variations of it) has been the subject of various publications [1, 3, 4, 7, 9, 11–19]. Hasse showed that N_{g}(d) has a Dirichlet density in case d is an odd prime [3], respectively d = 2 [4]. The latter case is of additional interest since N_{g}(2) is the set of prime divisors of the sequence {g^{k} + 1}_{k=1}^{∞}. (One says that an integer divides a sequence if it divides at least one term of the sequence.) Wiertelak [12] established that N_{g}(d) has a natural density δ_{g}(d) (around the same time Odoni [9] did so in the case d is a prime). In a later paper Wiertelak [15] proved, using sophisticated analytic tools, the following result (with Li(x) the logarithmic integral and with ω(d) = ∑_{p|d} 1), which gives the best known error term to date.

Theorem 1 [15]. We have

N_{g}(d)(x) = δ_{g}(d)Li(x) + O_{d,g} (\frac{x}{log^{3} x}(log log x)^{ω(d)+1}) .

Wiertelak also gave a formula for δ_{g}(d) which shows that this is always a positive rational number. A simpler formula for δ_{g}(d) (in case g > 0) has only recently been given by Pappalardi [10]. With some effort Pappalardi’s and Wiertelak’s expressions can be shown to be equivalent.

Mathematics Subject Classification (2000). 11N37, 11R45

In this note a simple identity for N_{g}(d)(x) will be established (given in Proposition 1). From this it is then inferred that N_{g}(d) has a natural density δ_{g}(d) that is given by (4), which seems to be the simplest expression involving field degrees known for δ_{g}(d). This expression is then readily evaluated.

In order to state Theorem 2 some notation is needed. Write g = ±g_{0}^{h}, where g_{0} is positive and not an exact power of a rational and h as large as possible. Let D(g_{0}) denote the discriminant of the field ℚ(\sqrt{g_{0}}). The greatest common divisor of a and b respectively the lowest common multiple of a and b will be denoted by (a, b), respectively [a, b]. Given an integer d, we denote by d^{∞} the supernatural number (sometimes called Steinitz number), ∏_{p|d} p^{∞}. Note that (v, d^{∞}) = ∏_{p|d} p^{ν_{p}(v)}.

Definition. Let d be even and let ϵ_{g}(d) be defined as in Table 1 with γ = max{0, ν_{2}(D(g_{0})/dh)}.

Table 1: ϵ_{g}(d)

\begin{matrix}g\γ & γ = 0 & γ = 1 & γ = 2 \\ g > 0 & −1/2 & 1/4 & 1/16 \\ g < 0 & 1/4 & −1/2 & 1/16 \end{matrix}

Note that γ ≤ 2. Also note that ϵ_{g}(d) = (−1/2)^{2^{γ}} if g > 0.

Theorem 2 We have

δ_{g}(d) = \frac{ϵ_{1}}{d(h, d^{∞})} ∏_{p|d} \frac{p^{2}}{p^{2} − 1},

with

ϵ_{1} = \{ \begin{matrix}1 & if 2 ∤ d; \\ 1 + 3(1 − sgn(g))(2^{ν_{2}(h)} − 1)/4 & if 2||d and D(g_{0}) ∤ 4d; \\ 1 + 3(1 − sgn(g))(2^{ν_{2}(h)} − 1)/4 + ϵ_{g}(d) & if 2||d and D(g_{0})|4d; \\ 1 & if 4|d, D(g_{0}) ∤ 4d; \\ 1 + ϵ_{|g|}(d) & if 4|d, D(g_{0})|4d. \end{matrix}

In particular, if g > 0, then

ϵ_{1} = \{ \begin{matrix}1 + (−1/2)^{2^{max\{0,ν_{2}(D(g_{0})/dh)\}}} & if 2|d and D(g_{0})|4d; \\ 1 & otherwise, \end{matrix}

and if h is odd, then

ϵ_{1} = \{ \begin{matrix}1 + (−1/2)^{2^{max\{0,ν_{2}(D(g)/dh)\}}} & if 2|d and D(g)|4d; \\ 1 & otherwise, \end{matrix}

Using Proposition 1 of Section 2 it is also very easy to infer the following result, valid under the assumption of the Generalized Riemann Hypothesis (GRH).

Theorem 3 Under GRH we have

N_{g}(d)(x) = δ_{g}(d)Li(x) + O_{d,g}(\sqrt{x} log^{ω(d)+1} x),

where the implied constant depends at most on d and g.

In Tables 2 and 3 (Section 6) a numerical demonstration of Theorem 2 is given.

2 The key identity

Let π_{L}(x) denote the number of unramified primes p ≤ x that split completely in the number field L. For integers r|s let K_{s,r} = ℚ(ζ_{s}, g^{1/r}).

The starting point of the proof of Theorem 2 is the following proposition. By r_{p}(g) the residual index of g modulo p is denoted (we have r_{g}(p) = [𝔽_{p} : ⟨g⟩]). Note that ord_{p}(g)r_{p}(g) = p − 1.

Proposition 1 We have N_{g}(d)(x) = ∑_{v|d^{∞}} ∑_{α|d} μ(α)π_{K_{dv,αv}}(x).

Proof. Let us consider the quantity ∑_{α|d} μ(α)π_{K_{dv,αv}}(x). A prime p counted by this quantity satisfies p ≤ x, p ≡ 1(mod dv) and r_{p}(g) = vw for some integer w. Write w = w_{1}w_{2}, with w_{1} = (w, d). Then the contribution of p to ∑_{α|d} μ(α)π_{K_{dv,αv}}(x) is ∑_{α|w_{1}} μ(α). We conclude that

∑_{α|d} μ(α)π_{K_{dv,αv}}(x) =

#\{p ≤ x : p ≡ 1(mod dv), v|r_{p}(g) and (\frac{r_{p}(g)}{v}, d) = 1\}.  (1)

It suffices to show that

N_{g}(d)(x) = ∑_{v|d^{∞}} #\{p ≤ x : p ≡ 1(mod dv), v|r_{p}(g) and (\frac{r_{p}(g)}{v}, d) = 1\}.

Let p be a prime counted on the right hand side. Note that it is counted only once, namely for v = (r_{p}(g), d^{∞}). From ord_{p}(g)r_{p}(g) = p − 1 it is then inferred that d|ord_{p}(g). Hence every prime counted on the right hand side is counted on the left hand side as well. Next consider a prime p counted by N_{g}(d)(x). It satisfies p ≡ 1(mod d). Note there is a (unique) integer v such that v|d^{∞}, p ≡ 1(mod dv) and (r_{p}(g)/v, d) = 1. Thus p is also counted on the right hand side. □

Remark 1. From (1) and Chebotarev’s density theorem it follows that

0 ≤ ∑_{α|d} \frac{μ(α)}{[K_{dv,αv} : ℚ]} ≤ \frac{1}{[K_{dv,v} : ℚ]}.  (2)

3 Analytic consequences

Using Proposition 1 it is rather straightforward to establish that N_{g}(d) has a natural density δ_{g}(d).

Lemma 1 Write g = g_{1}/g_{2} with g_{1} and g_{2} integers. Then

N_{g}(d)(x) = (δ_{g}(d) + O_{d,g} (\frac{(log log x)^{ω(d)}}{log^{1/8} x} )) Li(x),  (3)

where the implied constant depends at most on d and g and

δ_{g}(d) = ∑_{v|d^{∞}} ∑_{α|d} \frac{μ(α)}{[K_{dv,αv} : ℚ]}.  (4)

Corollary 1 The set N_{g}(d) has a natural density δ_{g}(d).

The proof of Lemma 1 makes use of the following consequence of the Brun-Titchmarsh inequality.

Lemma 2 Let π(x; l, k) = ∑_{p≤x, p≡l(mod k)} 1. Then

∑_{{v>z \atop v|d^{∞}}} π(x; dv, 1) = O_{d} (\frac{x}{log x} \frac{(log z)^{ω(d)}}{z} ) ,

uniformly for 3 ≤ z ≤ \sqrt{x}.

Proof. On noting that M_{d}(x) := #{v ≤ x : v|d^{∞}} ≤ (log x)^{ω(d)}/ log 2, it straightforwardly follows that

∑_{{v>z \atop v|d^{∞}}} \frac{1}{v} = ∫_{z}^{∞} \frac{dM_{d}(z)}{z} ≪_{d} \frac{(log z)^{ω(d)}}{z} .

By the Brun-Titchmarsh inequality we have π(x; w, 1) ≪ x/(φ(w) log(x/w)), where the implied constant is absolute and w < x. Thus

∑_{{z<v, dv≤x^{2/3} \atop v|d^{∞}}} π(x; dv, 1) ≪ \frac{x}{φ(d) log x} ∑_{{v>z \atop v|d^{∞}}} \frac{1}{v} ≪_{d} \frac{x}{log x} \frac{(log z)^{ω(d)}}{z} .  (5)

Using the trivial estimate π(x; d, 1) ≤ x/d we see that

∑_{{dv>x^{2/3} \atop d|v^{∞}}} π(x; dv, 1) ≤ ∑_{{dv>x^{2/3} \atop v|d^{∞}}} \frac{x}{dv} ≤ ∑_{{w>x^{2/3} \atop w|d^{∞}}} \frac{x}{w} ≪_{d} x^{1/3}(log x)^{ω(d)}.  (6)

On combining (5) and (6) the proof is readily completed. □

Proof of Lemma 1. From [10, Lemma 2.1] we recall that there exist absolute constants A and B such that if v ≤ B(log x)^{1/8}/d, then

π_{K_{dv,αv}}(x) = \frac{Li(x)}{[K_{dv,αv} : ℚ]} + O_{g}(xe^{− \frac{A}{dv} \sqrt{log x}}).  (7)

Let y = B(log x)^{1/8}/d. From the proof of Proposition 1 we see that

N_{g}(d)(x) = ∑_{{v|d^{∞} \atop v≤y}} ∑_{α|d} μ(α)π_{K_{dv,αv}}(x) + O (∑_{{v>y \atop v|d^{∞}}} π(x; dv, 1)) = I_{1} + O(I_{2}),

say. By Lemma 2 we obtain that I_{2} = O(x(log log x)^{ω(d)} log^{−9/8} x). Now, by (7), we obtain

I_{1} = ∑_{{v|d^{∞} \atop v≤y}} ∑_{α|d} \frac{μ(α)}{[K_{dv,αv} : ℚ]} + O_{d,g}(y \frac{x}{log^{5/4} x}).

Denote the latter double sum by I_{3}. Keeping in mind Remark 1 we obtain

I_{3} = δ_{g}(d) + O (∑_{{v|d^{∞} \atop v>y}} ∑_{α|d} \frac{μ(α)}{[K_{dv,αv} : ℚ]}) .

Using (2) and Lemma 3 it follows that

∑_{{v|d^{∞} \atop v>y}} ∑_{α|d} \frac{μ(α)}{[K_{dv,αv} : ℚ]} = O (∑_{{v|d^{∞} \atop v>y}} \frac{1}{[K_{dv,v} : ℚ]}) = O(\frac{1}{φ(d)} ∑_{{v|d^{∞} \atop v>y}} \frac{h}{v^{2}} )

= O_{d}(\frac{h(log y)^{ω(d)}}{y}) = O_{d,g} (\frac{(log y)^{ω(d)}}{y} ) ,

and hence

I_{3} = δ_{g}(d) + O_{d,g} (\frac{(log y)^{ω(d)}}{y} ) .

The result follows on collecting the various estimates. □

4 The evaluation of the density δ_{g}(d)

A crucial ingredient in the evaluation of δ_{g}(d) is the following lemma.

Lemma 3 [6]. Write g = ±g_{0}^{h}, where g_{0} is positive and not an exact power of a rational. Let D(g_{0}) denote the discriminant of the field ℚ(\sqrt{g_{0}}). Put m = D(g_{0})/2 if ν_{2}(h) = 0 and D(g_{0}) ≡ 4(mod 8) or ν_{2}(h) = 1 and D(g_{0}) ≡ 0(mod 8), and m = [2^{ν_{2}(h)+2}, D(g_{0})] otherwise. Put

n_{r} = \{ \begin{matrix}m & if g < 0 and r is odd; \\ [2^{ν_{2}(hr)+1}, D(g_{0})] & otherwise. \end{matrix}

We have

[K_{kr,k} : ℚ] = [ℚ(ζ_{kr}, g^{1/k}) : ℚ] = \frac{φ(kr)k}{ϵ(kr, k)(k, h)},

where, for g > 0 or g < 0 and r even we have

ϵ(kr, k) = \{ \begin{matrix}2 & if n_{r}|kr; \\ 1 & if n_{r} ∤ kr, \end{matrix}

and for g < 0 and r odd we have

ϵ(kr, k) = \{ \begin{matrix}2 & if n_{r}|kr; \\ \frac{1}{2} & if 2|k and 2^{ν_{2}(h)+1} ∤ k; \\ 1 & otherwise. \end{matrix}

Remark. Note that if h is odd, then n_{r} = [2^{ν_{2}(r)+1}, D(g)]. Note that n_{r} = n_{ν_{2}(r)}.

The ‘generic’ degree of [K_{dv,αv} : ℚ] equals φ(dv)αv/(αv, h) and on substituting this value in (4) we obtain the quantity S_{1} which is evaluated in the following lemma.

Lemma 4 We have

S_{1} := ∑_{v|d^{∞}} ∑_{α|d} \frac{μ(α)(αv, h)}{φ(dv)αv} = S(d, h),

where

S(d, h) := \frac{1}{d(h, d^{∞})} ∏_{p|d} \frac{p^{2}}{p^{2} − 1}.

Proof. Since for v|d^{∞} we have φ(dv) = vφ(d), we can write

S_{1} = \frac{1}{φ(d)} ∑_{v|d^{∞}} ∑_{α|d} \frac{μ(α)(αv, h)}{αv^{2}} = \frac{1}{φ(d)} ∑_{v|d^{∞}} \frac{(v, h)}{v^{2}} ∑_{α|d} \frac{μ(α)(αv, h)}{α(v, h)}.

The expression in the inner sum is multiplicative in α and hence

∑_{α|d} \frac{μ(α)(αv, h)}{α(v, h)} = ∏_{p|d} (1 − \frac{(pv, h)}{p(v, h)}) = \{ \begin{matrix}\frac{φ(d)}{d} & if (h, d^{∞})|(v, d^{∞}); \\ 0 & otherwise. \end{matrix}

On noting that (v, h)/v^{2} is multiplicative in v and that for k ≥ ν_{p}(h)

∑_{r=k}^{∞} \frac{(p^{r}, h)}{p^{2r}} = \frac{p^{ν_{p}(h)+2−2k}}{p^{2} − 1} ,

one concludes that

S_{1} = \frac{1}{d} ∑_{{v|d^{∞} \atop (h,d^{∞})|v}} \frac{(v, h)}{v^{2}} = \frac{1}{d} ∏_{p|d} ∑_{r≥ν_{p}(h)} \frac{(p^{r}, h)}{p^{2r}} = \frac{1}{d} ∏_{p|d} \frac{p^{2−ν_{p}(h)}}{p^{2} − 1} = S(d, h).

This completes the proof. □ Remark. Note that the condition (h, d^{∞})|(v, d^{∞}) is equivalent with ν_{p}(v) ≥ ν_{p}(h) for all primes p dividing d. By a minor modification of the proof of the latter result we infer: Lemma 5 Let k ≥ 0 be an integer. Then

S_{2}(k) := ∑_{{v|d^{∞} \atop ν_{2}(v)≥ν_{2}(h)+k}} ∑_{α|d} \frac{μ(α)(αv, h)}{φ(dv)αv} = 4^{−k}S(d, h).

The next lemma gives an evaluation of yet another variant of S_{1}. Lemma 6 Let D be a fundamental discrimant. Then

S_{3}(D) := ∑_{{v|d^{∞} \atop [2^{ν_{2}(hd/α)+1},D]|dv}} ∑_{α|d} \frac{μ(α)(αv, h)}{φ(dv)αv} = \{ \begin{matrix}4^{−γ}S(d, h) & if 2|d, D|4d and γ ≥ 1; \\ −\frac{S(d,h)}{2} & if 2|d, D|4d and γ = 0; \\ 0 & otherwise, \end{matrix}

where γ = max{0, ν_{2}(D/dh)}.

Proof. The integer [2^{ν_{2}(hd/α)+1}, D] is even and is required to divide d^{∞}, hence S_{3}(D) = 0 if d is odd. Assume that d is even. If D has an odd prime divisor not divinding d, then D ∤ d^{∞} and hence S_{3}(D) = 0. On noting that ν_{2}(D) ≤ ν_{2}(4d) and that the odd part of D is squarefree, it follows that if S_{3}(D) ≠ 0, then D|4d. So assume that 2|d and D|4d. Note that the condition [2^{ν_{2}(hd/α)+1}, D]|dv is equivalent with ν_{2}(v) ≥ ν_{2}(h) + max{1, ν_{2}(D/dh)} for the α that are odd, and ν_{2}(v) ≥ ν_{2}(h) + γ for the even α. Thus if γ ≥ 1 the condition [2^{ν_{2}(hd/α)+1}, D]|dv is equivalent with ν_{2}(v) ≥ ν_{2}(h) + γ and then, by Lemma 5, S_{3}(D) = S_{2}(γ) = 4^{−γ}S(d, h). If γ = 0 then

S_{3}(D) = S_{2}(0) − ∑_{{v|d^{∞} \atop ν_{2}(v)=ν_{2}(h)}} ∑_{{α|d \atop 2∤α}} \frac{μ(α)(αv, h)}{φ(dv)αv}.

By Lemma 5 it follows that S_{2}(0) = S(d, h). A variation of Lemma 4 yields that the latter double sum equals 3S(d, h)/2. □

Remark. Put

ϵ_{2}(D) = \{ \begin{matrix}(−1/2)^{2^{max\{0,ν_{2}(D/dh)\}}} & if 2|d and D|4d; \\ 0 & otherwise. \end{matrix}

Note that Lemma 6 can be rephrased as stating that if D is a fundamental discriminant, then S_{3}(D) = ϵ_{2}(D)S(d, h).

Let g > 0. It turns out that ord_{p}(g) is very closely related to ord_{p}(−g) and this can be used to express N_{−g}(d)(x) in terms of N_{g}(∗)(x). From this δ_{−g}(d) is then easily evaluated, once one has evaluated δ_{g}(d).

Lemma 7 Let g > 0. Then

N_{−g}(d)(x) = \{ \begin{matrix}N_{g}(\frac{d}{2})(x) + N_{g}(2d)(x) − N_{g}(d)(x) + O(1) & if d ≡ 2(mod 4); \\ N_{g}(d)(x) + O(1) & otherwise. \end{matrix}

In particular,

δ_{−g}(d) = \{ \begin{matrix}δ_{g}(\frac{d}{2}) + δ_{g}(2d) − δ_{g}(d) & if d ≡ 2(mod 4); \\ δ_{g}(d) & otherwise. \end{matrix}

The proof of this lemma is a consequence of Corollary 1 and the following observation.

Lemma 8 Let p be odd and g ≠ 0 be a rational number. Suppose that ν_{p}(g) = 0. Then

ord_{p}(−g) = \{ \begin{matrix}2ord_{p}(g) & if 2 ∤ ord_{p}(g); \\ ord_{p}(g)/2 & if ord_{p}(g) ≡ 2(mod 4); \\ ord_{p}(g) & if 4|ord_{p}(g). \end{matrix}

Proof. Left to the reader. □

Remark. It is of course also possible to evaluate δ_{g}(d) for negative g using the expression (4) and Lemma 3, however, this turns out to be rather more cumbersome than proceeding as above.

5 The proofs of Theorems 2 and 3

Proof of Theorem 2. By Lemma 1 it suffices to show that

∑_{v|d^{∞}} ∑_{α|d} \frac{μ(α)}{[K_{dv,αv} : ℚ]} = ϵ_{1}S(d, h)

If g > 0, then it follows by Lemma 3 that δ_{g}(d) = S_{1} +S_{3}(D(g_{0})) and by Lemmas 4 and 6 (with D = D(g_{0})), the claimed evaluation then results in this case. If h is odd, then similarly, δ_{g}(d) = S_{1} + S_{3}(D(g)) (cf. the remark following Lemma 3) and, again by Lemma 4 and 6, the claimed evaluation then is deduced in this case. If g < 0, the result follows after some computation on invoking Lemma 7 and the result for g > 0. □

Proof of Theorem 3. Recall that π_{L}(x) denotes the number of unramified primes p ≤ x that split completely in the number field L. Under GRH it is known, cf. [5], that

π_{L}(x) = \frac{Li(x)}{[L : ℚ]} + O (\frac{\sqrt{x}}{[L : ℚ]} log(d_{L}x^{[L:ℚ]})) ,

where d_{L} denotes the absolute discriminant of L. From this it follows on using the estimate log |d_{K_{dv_{1},αv}}| ≤ dv(log(dv) + log |g_{1}g_{2}|) from [6] that, uniformly in v,

π_{K_{dv,αv}}(x) = \frac{Li(x)}{[K_{dv,αv} : ℚ]} + O_{d,g}(\sqrt{x} log x),

where α is an arbitrary divisor of d. On noting that in Proposition 1 we can restrict to those integers v satisfying dv ≤ x and hence the number of nonzero terms in Proposition 1 is bounded above by 2^{ω(d)}(log x)^{ω(d)}, the result easily follows. □

6 Some examples

In this section we provide some numerical demonstration of our results.

The numbers in the column ‘experimental’ arose on counting how many primes p ≤ p_{10^{8}} = 2038074743 with ν_{p}(g) = 0, satisfy d|ord_{p}(g).

Table 2: The case g > 0

g g_{0} h D(g_{0}) d  ϵ_{1}  δ_{g}(d)  numerical experimental
2 2 1  8  2 17/16 17/24 0.70833333 ⋯ 0.70831919
2 2 1  8  4 5/4 5/12 0.41666666 ⋯ 0.41667021
2 2 1  8  8 1/2 1/12 0.08333333 ⋯ 0.08333144
3 3 1 12 11 1 11/120 0.09166666 ⋯ 0.09165950
3 3 1 12 12 1/2 1/16 0.06250000 ⋯ 0.06249098
4 2 2  8  5  1  5/24 0.20833333 ⋯ 0.20833328
4 2 2  8  6 5/4 5/32 0.15625000 ⋯ 0.15625824

Table 3: The case g < 0

g g_{0} h D(g_{0}) d  ϵ_{1}  δ_{g}(d)  numerical experimental
-2 3 1  8  2 17/16 17/24 0.70833333 ⋯ 0.70835101
-2 2 1  8  4 5/4 5/12 0.41666666 ⋯ 0.41667021
-2 2 1  8  6 17/16 17/64 0.26562500 ⋯ 0.26562628
-3 3 1 12 5  1  5/24 0.20833333 ⋯ 0.20834107
-3 3 1 12 12 1/2 1/16 0.06250000 ⋯ 0.06249098
-4 2 2  8  2  2  2/3 0.66666666 ⋯ 0.66666122
-4 2 2  8  4 1/2 1/8 0.08333333 ⋯ 0.08333144
-9 3 2 12 2 5/2 5/6 0.83333333 ⋯ 0.83333215
-9 3 2 12 6 11/4 11/32 0.34375000 ⋯ 0.34375638

Acknowledgement. I like to thank Francesco Pappalardi for sending me his paper [10]. Theorem 1.3 in that paper made me realize that a relatively simple formula for δ_{g}(d) exists. The data in the tables are produced by a C^{++} program kindly written by Yves Gallot.

References

[1] C. Ballot, Density of prime divisors of linear recurrences, Mem. Amer. Math. Soc. 115 (1995), no. 551, viii+102 pp..

[2] K. Chinen and L. Murata, On a distribution property of the residual order of a(mod p). I, J. Number Theory 105 (2004), 60–81.

[3] H. Hasse, Über die Dichte der Primzahlen p, für die eine vorgegebene ganzrationale Zahl a ≠ 0 von durch eine vorgegebene Primzahl l ≠ 2 teilbarer bzw. unteilbarer Ordnung mod. p ist, Math. Ann. 162 (1965/1966), 74–76.

[4] H. Hasse, Über die Dichte der Primzahlen p, für die eine vorgegebene ganzrationale Zahl a ≠ 0 von gerader bzw.ungerader Ordnung mod. p ist, Math. Ann. 166 (1966), 19–23.

[5] S. Lang, On the zeta function of number fields, Invent. Math. 12 (1971), 337–345.

[6] P. Moree, On the distribution of the order and index of g(mod p) over residue classes I, arXiv:math.NT/0211259, J. Number Theory, to appear.

[7] P. Moree, Asymptotically exact heuristics for prime divisors of the sequence {a^{k} + b^{k}}_{k=1}^{∞}, arXiv:math.NT/0311483, submitted.

[8] L. Murata and K. Chinen, On a distribution property of the residual order of a(mod p). II, J. Number Theory 105 (2004), 82–100.

[9] R. W. K. Odoni, A conjecture of Krishnamurthy on decimal periods and some allied problems, J. Number Theory 13 (1981), 303–319.

[10] F. Pappalardi, Square free values of the order function, New York J. Math. 9 (2003), 331-344.

[11] K. Wiertelak, On the density of some sets of primes. I, Acta Arith. 34 (1977/78), 183–196.

[12] K. Wiertelak, On the density of some sets of primes. II, Acta Arith. 34 (1977/78), 197–210.

[13] K. Wiertelak, On the density of some sets of primes. III, Funct. Approx. Comment. Math. 10 (1981), 93–103.

[14] K. Wiertelak, On the density of some sets of primes. III. Studies in pure mathematics, 761–773, Birkhäuser, Basel, 1983.

[15] K. Wiertelak, On the density of some sets of primes. IV, Acta Arith. 43 (1984), 177–190.

[16] K. Wiertelak, On the density of some sets of integers, Funct. Approx. Comment. Math. 19 (1990), 71–76.

[17] K. Wiertelak, On the density of some sets of primes p, for which (ord_{p} b, n) = d, Funct. Approx. Comment. Math. 21 (1992), 69–73.

[18] K. Wiertelak, On the distribution of the smallest natural numbers having order mod p not coprime with a given integer, Acta Math. Hungar. 80 (1998), 271–284.

[19] K. Wiertelak, On the density of some sets of primes p, for which n|ord_{p}a, Funct. Approx. Comment. Math. 28 (2000), 237–241.

Max-Planck-Institut für Mathematik, Vivatsgasse 7, D-53111 Bonn, Germany.

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