ON THE ORDER OF a (mod p) Paul Erdös^{1} and M. Ram Murty

§1. Introduction

Let a be a fixed natural number greater than unity. For each prime p not dividing a, let f(p) denote the order of a (mod p). A classical conjecture of E. Artin [1] states that f(p) = p − 1 for infinitely many primes p. We are interested in obtaining a good lower bound for f(p) for almost all prime numbers p (that is, for all but o(x/ log x) prime numbers p ≤ x).

It is easy to see that

f(p) > \sqrt{p}/ log p

for all but o(x/ log x) primes p ≤ x. Indeed, if f(p) < z, then p divides the product

V = ∏_{t<z}(a^{t} − 1).

Since a natural number has at most O(log n/ log log n) prime factors, we find that V has at most

≪ ∑_{t<z} \frac{t}{log t} ≪ \frac{z^{2}}{log z}

prime factors. Thus, the inequality f(p) < \sqrt{p}/ log p can hold for at most O(x/ log^{3} x) primes p ≤ x.

It seems difficult to improve this simple argument to show that f(p) > \sqrt{p} for almost all primes. By a different argument, we will prove:

Theorem 1. Let ϵ(p) be any function tending to zero as p→∞. For all but o(x/ log x) primes p ≤ x,

f(p) ≥ p^{\frac{1}{2} +ϵ(p)}.

This theorem will be a consequence of a more general theorem concerning divisors of p − 1. Indeed, we prove:

1 This paper was written by the authors in 1987 while Paul Erdös was visiting McGill. We had planned to work on an expanded version refining Theorem 2 and neither of the authors found the time or the opportunity to continue the work. It is published here in the hope that others may continue the task.

Theorem 2. Let δ > 0 and fixed. Let ϵ(x) be any function tending to zero as x→∞. The number of primes p ≤ x such that p − 1 has a divisor in the interval (x^{δ}, x^{δ+ϵ(x)}) is o(x/ log x).

Since f(p) divides p − 1, Theorem 1 follows from Theorem 2 upon taking δ = 1/2.

Theorem 2 is to be viewed as the p−1 analogue of a theorem of Erdös [3], who proved that the number of integers n ≤ x having a divisor in the interval (x^{δ}, x^{δ+ϵ(x)}) is o(x). Our proof of Theorem 2 follows very closely to the method and notation of Erdös [3]. The method, however, cannot give a better estimate for the exceptional set than o(x/ log x). By an alternate method, we deduce:

Theorem 3. There exists an α > 0 and a δ > 0 such that

f(p) ≥ \sqrt{p} exp((log p)^{δ})

for all but O(x/(log x)^{1+α}) primes p ≤ x.

In [11], it was proved that

∑_{p≤x} \frac{1}{f(p)} ≪ \sqrt{x},

and it was conjectured that the sum is in fact O(x^{ϵ}). It was also noted that if the sum is O(x^{1/4}), then Artin’s conjecture follows. Theorem 3 allows us to obtain the following improvement.

Corollary. For some δ > 0,

∑_{p≤x} \frac{1}{f(p)} ≪ \frac{\sqrt{x}}{(log x)^{1+δ}} .

If we assume the analogue of the Riemann hypothesis for zeta functions of certain number fields, then it is possible to prove more than Theorem 1.

Theorem 4. Let ϵ(x) be any function tending to zero as x→∞. For each squarefree d, let ζ_{d}(s) denote the Dedekind zeta function of the algebraic number field

ℚ(exp(2π\sqrt{−1}/d), a^{1/d})

and ζ(s) the usual Riemann zeta function. If all the non-trivial zeroes of ζ_{d}(s) lie on Re(s) = 1/2, then

f(p) ≥ p/ϵ(p)

for all but o(x/ log x) primes p ≤ x.

It is not difficult to generalize these results to an arbitrary subgroup Γ ⊆ ℚ^{∗} of rank r (say). Suppose Γ is generated by the mutually coprime numbers a_{1}, a_{2}, ..., a_{r}. For all primes p not dividing the denominators of a_{1}, ..., a_{r}, we can define f_{Γ}(p) to be the order of Γ (mod p). The previous theorems can be viewed as the case r = 1. The methods are analogous. The key idea is to use an appropriate analogue of Lemma 14 of [5] in conjunction with Theorem 2 to deduce the following:

Theorem 5. Let ϵ(x) be any function tending to zero as x→∞.

(1) For all but o(x/ log x) primes p ≤ x,

f_{Γ}(p) ≥ p^{\frac{r}{r+1} +ϵ(p)}.

(2) There exists an α > 0 and a δ > 0 such that

f_{Γ}(p) ≥ p^{\frac{r}{r+1}} exp((log p)^{δ})

for all but O(x/(log x)^{1+α}) primes p ≤ x.

(3) For each squarefree number d, let ζ_{d,i}(s) denote the Dedekind zeta function of

ℚ(exp(2π\sqrt{−1}/d), a_{i}^{1/d}).

If for each 1 ≤ i ≤ r, ζ_{d,i}(s) has no zeroes in the region Re(s) > r/r + 1, then

f_{Γ}(p) ≥ p/ϵ(p)

for all but o(x/ log x) primes p ≤ x.

§2. Lemmas.

Denote by π(x) the number of primes ≤ x. Let us factor p − 1 = uD where u is a divisor of p − 1 in the stated interval. Set ν = − log ϵ(x). Now write

u = AB where A is a number composed of primes ≤ x^{ϵ(x)}, B is a number composed of primes > x^{ϵ(x)}.

Lemma 1. Let A be as above. The number of primes p ≤ x for which A is greater than x^{ϵ(x)ν} is O(π(x)/ν).

Proof. If S is the number of primes in question, then by an analogue of Legendre’s formula,

Sϵ(x)ν log x ≤ ∑_{q≤x^{ϵ}}{π(x, q) + π(x, q^{2}) + ⋯} log q

where q denotes a prime number and π(x, q^{a}) is the number of primes ≤ x which are ≡ 1 (mod q^{a}). We write the sum on the right hand side as ∑_{I} + ∑_{II} where in the first sum a = 1 and in the second sum a ≥ 2. An application of the Bombieri-Vinogradov theorem shows that the first sum is ≪ ϵ(x)x. For the second sum, we begin by observing

∑_{q>log^{3} x}\{π(x, q^{2}) + ⋯\} log q ≪ log x ∑_{q>log^{3} x} \frac{x}{q(q − 1)}

obtained by using the trivial bound π(x, q^{a}) ≤ x/q^{a}. The contribution from these terms to the sum is seen to be O(x/ log x). If q^{a} ≤ x^{1/2}, we can apply the Brun-Titchmarsh inequality [6 ] to see that

∑_{{q≤x^{ϵ(x)} \atop q^{a}≤x^{1/2},a≥2}}\{π(x, q^{a})\} log q ≪ \frac{x}{log x}.

It remains to consider the contribution to ∑_{II} of the primes q ≤ log^{3} x for which q^{a} > x^{1/2}. But in this case,

a ≥ b = \frac{log x}{6 log log x}

and the contribution is for some constant c_{1} > 0,

≪ ∑_{{q≤log^{3} x \atop a≥b}} \frac{x}{q^{b−1}(q − 1)} log q ≪ x log^{3} x exp(−c_{1} \frac{log x}{log log x}),

which is negligible. Hence,

S ≪ π(x)/ν.

Lemma 1 implies that in trying to prove Theorem 2, we can suppose that A ≤ x^{ϵ(x)ν}. Thus, B lies in the interval

J = (x^{δ−ϵ(x)ν}, x^{δ+ϵ(x)})

and all its prime factors lie in the interval K = (x^{ϵ(x)}, x^{δ+ϵ(x)}). The next lemma allows us to confine our attention to squarefree numbers in J.

Lemma 2. If B is divisible by a square of a prime, the number of primes p ≤ x such that p − 1 is divisible by such a B is o(x/ log x).

Proof. This is immediate from the Brun-Titchmarsh inequality. Indeed, since all the prime divisors of B are ≥ x^{ϵ(x)}, the number in question is bounded by

∑_{q≥x^{ϵ(x)}} π(x, q^{2}).

Using the trivial bound π(x, q^{2}) ≤ x/q^{2} gives

∑_{x^{ϵ(x)}≤q log^{2} x} π(x, q^{2}) + ∑_{q>log^{2} x} \frac{x}{q^{2}} = ∑_{x^{ϵ(x)}≤q≤log^{2} x} π(x, q^{2}) + O(\frac{x}{log^{2} x}).

Now using the Brun-Titchmarsh inequality, the result is immediate.

Lemma 3. For θ > 1,

(i)  ∑_{k>θy} \frac{y^{k}}{k!} ≤ θ^{−θy}e^{θy}

and for θ < 1,

(ii)  ∑_{k<θy} \frac{y^{k}}{k!} ≤ θ^{−θy}e^{θy},

provided y > 1.

Proof. We have

∑_{k>θy} \frac{y^{k}}{k!} = ∑_{k>θy} \frac{(θy)^{k}}{k!} θ^{−k} ≤ θ^{−θy}e^{θy},

for θ > 1. This proves (i). To prove (ii), we first note that

e^{k} ≥ k^{k}/k!.

For y > 1, observe that y^{k}/k! is an increasing function of k when k < θy and θ < 1. Hence,

∑_{k<θy} \frac{y^{k}}{k!} ≤ (θ)^{−θy}e^{θy}.

A version of Lemma 3 appears in [10]. We insert it here because it makes our subsequent argument easier to follow. Using the notation of [3], we will denote by B_{i}^{∗} a number lying in the interval J which has no more than 2ν/3 prime factors from K. A B_{i}^{+} will denote a number lying in J whose number of prime factors from K is at least 2ν/3 but less than 4ν/3. A B_{i}^{(r)} will denote a number from J with exactly r prime factors in K.

Lemma 4. There is a positive constant c such that

∑_{i=1}^{∞} \frac{1}{ϕ(B_{i}^{∗})} ≤ ϵ(x)^{c},

where ϕ denotes Euler’s function.

Proof. First we estimate

∑_{i=1}^{∞} \frac{1}{ϕ(B_{i}^{(r)})}.

If

B_{i}^{(r)} = p_{1}p_{2} ⋯ p_{r},

then p_{r} > (B_{i}^{(r)})^{1/r} so that

(1)  p_{1} ⋯ p_{r−1} < x^{(δ+ϵ(x))(r−1)/r}

and so the sum of the reciprocals of ϕ(B_{i}^{(r)}) of which the first r − 1 prime factors are p_{1}, ..., p_{r−1} is not greater than

\frac{1}{ϕ(p_{1} ⋯ p_{r−1})} ^{∑′} \frac{1}{p_{r} − 1}

where the dash on the summation means that p_{r} runs through the interval

(\frac{x^{δ−ϵ(x)ν}}{p_{1} ⋯ p_{r−1}} , \frac{x^{δ+ϵ(x)}}{p_{1} ⋯ p_{r−1}} ) .

Since

∑_{U≤p≤UV} \frac{1}{p} = log log UV − log log U + O(\frac{1}{log V} ),

we find

∑_{U≤p≤UV} \frac{1}{p} < \frac{log V}{log U} + O(\frac{1}{log U}).

Therefore, taking

U = \frac{x^{δ−ϵ(x)ν}}{p_{1} ⋯ p_{r−1}} , V = x^{ϵ(x)(ν+1)}

in the above estimate, we find on using (1),

∑′ \frac{1}{p_{r} − 1} ≪ \frac{r(ν + 1)ϵ(x)}{δ − ϵ(x)(νr + r − 1)}.

Since, r ≤ 4ν/3, ϵ(x)(rν + r − 1) ≪ ϵ(x)ν^{2} and so

∑′ \frac{1}{p_{r} − 1} ≪ ϵ(x)ν^{2}.

Hence

∑_{i=1}^{∞} \frac{1}{ϕ(B_{i}^{(r)})} ≪ \frac{ϵ(x)ν^{2}}{(r − 1)!} (∑_{p∈K} \frac{1}{p})^{r−1}

which is

≪ \frac{ϵ(x)ν^{2}}{(r − 1)!}(ν + 1)^{r−1}.

Thus,

∑_{i=1}^{∞} \frac{1}{ϕ(B_{i}^{∗})} = ∑_{1≤r≤2ν/3} ∑_{i=1}^{∞} \frac{1}{ϕ(B_{i}^{(r)})}

≪ ϵ(x)ν^{2} ∑_{1≤r≤2ν/3} \frac{(ν + 1)^{r−1}}{(r − 1)!}

≪ ϵ(x)ν^{2}(2/3)^{−2(ν+1)/3}e^{2(ν+1)/3}

by Lemma 3. The latter quantity is easily seen to be

≪ ϵ(x)^{c}ν^{3}

for some positive constant c > 0. This completes the proof. Lemma 5.

∑_{i=1}^{∞} \frac{1}{ϕ(B_{i}^{+})} ≪ ν^{2}.

Proof. As in the previous lemma, we find

∑_{i=1}^{∞} \frac{1}{ϕ(B_{i}^{+})} ≤ ∑_{2ν/3≤r≤4ν/3} ∑_{i=1}^{∞} \frac{1}{ϕ(B_{i}^{(r)})}

≪ ϵ(x)ν^{2} ∑_{2ν≤r≤4ν/3} \frac{(ν + 1)^{r−1}}{(r − 1)!}

≪ ϵ(x)ν^{2}e^{ν+1}

≪ ν^{2}.

Lemma 6. The number of primes p ≤ x such that p − 1 is divisible by more than 4ν/3 primes from the interval K is o(x/ log x).

Proof. This follows from Turán’s normal order method. For completeness, we give a sketch. Let ν_{K}(p−1) denote the number of prime factors of p−1 lying in K. Then, letting ρ = min (1/6, δ), we find

∑_{p≤x} ν_{K}(p − 1) = ∑_{p≤x} ( ∑_{{x^{ϵ(x)}≤q≤x^{ρ} \atop q|p−1}} +O(1))

which is

= ∑_{x^{ϵ(x)}≤q≤x^{ρ}} π(x, q) + O(x/ log x).

Using the Bombieri-Vinogradov theorem, we deduce that

∑_{p≤x} ν_{K}(p − 1) = π(x)ν + O(x/ log x).

Similarly, we deduce that

∑_{p≤x} ν_{K}^{2}(p − 1) = π(x)ν^{2} + O(π(x)ν)

so that

∑_{p≤x} (ν_{K}(p − 1) − ν)^{2} = O(π(x)ν).

Therefore, the number of primes p ≤ x satisfying ν_{K}(p − 1) ≥ (4/3)ν is O(π(x)/ν). This completes the proof of the lemma.

§3. Proof of Theorem 2.

By lemma 1, we can suppose that A ≤ x^{ϵ(x)ν} and so B ∈ J. If B has less than 2ν/3 prime factors from K, then by the Brun-Titchmarsh inequality the number of primes divisible by such a B is

≪ ∑_{i=1}^{∞} \frac{x}{ϕ(B_{i}^{∗}) log x}.

This quantity is by lemma 4,

≪ \frac{x}{log x}ϵ(x)^{c} = o(x/ log x).

If B has more than 4ν/3 prime factors from K, then by lemma 6, the number of primes p such that p − 1 is divisible by such a B is o(x/ log x). Thus, in our notation, B is a B_{i}^{+} and p − 1 has the form

p − 1 = tB_{i}^{+}

where t has no prime factors in the interval K. Fixing B_{i}^{+}, we count the number of integers t ≤ x/B_{i}^{+} such that t is not divisible by any prime in the interval K and tB_{i}^{+} + 1 is not divisible by any prime ≤ x^{1/2}. Defining

ω(p) = \{ \begin{matrix}1 & if p ≤ x^{ϵ(x)} \\ 2 & if x^{ϵ(x)} < p ≤ x^{1/2} \\ 1 & if p|B_{i}^{+} \end{matrix}

we see by Brun’s sieve that the number of such t is

≪ \frac{x}{B_{i}^{+}} ∏_{p≤x^{1/2}} (1 − \frac{ω(p)}{p}) ≪ \frac{x}{ϕ(B_{i}^{+})} \frac{ϵ(x)}{log x}.

Summing over B_{i}^{+} using lemma 5 yields that the sum is

≪ \frac{x}{log x}ϵ(x)ν^{2} = o(x/ log x).

This completes the proof of Theorem 2.

§4. Proof of Theorem 3.

In view of the remarks made at the outset of the paper, it suffices to consider the size of the set

S = \{p ≤ x : \sqrt{x}/ log x < f(p) ≤ \sqrt{x} exp(log^{δ} x)\}

for a suitable δ > 0 to be chosen later. If p is an element of this set, then p − 1 can be written as a product of two numbers u and v, each factor approximately \sqrt{x}, since we can assume, without loss, p ≥ x/ log^{2} x. More precisely,

p − 1 = uv, \sqrt{x}/ log x < u < \sqrt{x} exp(log^{δ} x), \sqrt{x} exp(− log^{δ} x) < v < \sqrt{x} log x.

We now estimate the number of such primes. Let Ω(n) denote the number of prime factors of n, counted with multiplicity. Then, if both conditions

Ω(u) > \frac{2}{3} log log x

Ω(v) > \frac{2}{3} log log x

hold, then Ω(p − 1) > 1.3 log log x. By a classical theorem of Erdös [4], the number of such primes p ≤ x is

O(\frac{x}{log^{η} x})

for some η > 0. Therefore, we can suppose that one of the above inequalities fails. Without loss of generality, suppose that

Ω(v) ≤ \frac{2}{3} log log x.

Let P (v) denotes the greatest prime factor of v. If

(2)  P (v) < exp(log^{1−ϵ} x)

then by a classical theorem of de Bruijn [2], the number of such v ≤ x/u is

≪ \frac{x}{u} exp(− log^{ϵ} x).

Thus, if (2) holds, the number of elements of S cannot exceed

\begin{matrix}∑ & ′ \\ u \end{matrix} \frac{x}{u} exp(− log^{ϵ} x)

where the dash on the sum indicates that u is in the specified range of S. But

\begin{matrix}∑ & ′ \\ u \end{matrix} \frac{1}{u} ≪ log^{δ} x

and so the number of primes p ∈ S satisfying (2) cannot exceed

x exp(−c_{2} log^{ϵ} x)

for some positive constant c_{2}. We may therefore suppose that

(3)  p − 1 = uv_{1}q

where q is a prime greater than exp(log^{1−ϵ} x). For fixed u and v_{1}, the number of solutions of (3) is by Brun’s sieve

≪ \frac{x}{uv_{1} log^{2}(x/uv_{1})}.

As

uv_{1} ≤ x exp(−c_{1} log^{1−ϵ} x)

the number of solutions of (3) is

≪ \frac{x}{uv_{1} log^{2−ϵ} x}.

Since

Ω(v_{1}) < \frac{2}{3} log log x

and the number of natural numbers satsifying this inequality is [4]

O (\frac{x}{log^{β} x}) ,

for some β > 0, and therefore by partial summation,

∑_{Ω(v_{1})<2 log log x/3} \frac{1}{v_{1}} ≪ (log x)^{1−β}.

Hence, the total number of elements of S cannot exceed

\frac{x}{(log x)^{1+β−ϵ}} \begin{matrix}∑ & ′ \\ u \end{matrix} \frac{1}{u} ≪ \frac{x}{(log x)^{1+β−ϵ−δ}}

so that if we choose δ < β, we obtain the desired result. This completes the proof of Theorem 3.

To prove the corollary, we break the sum into three parts:

∑_{f(p)≤y} + ∑_{y<f(p)≤z} + ∑_{z<f(p)≤x} .

By the remarks made at the outset of the paper, the number of primes p such that f(p) ≤ u is O(u^{2}/ log u). Hence, by partial summation, the first sum is O(y/ log y). The third sum is trivially O(x/z log x). If we choose

y = \sqrt{x}/ log^{β} x, z = \sqrt{x} exp(log^{δ} x)

then Theorem 3 implies that the middle sum is

≪ \frac{\sqrt{x}}{(log x)^{1+α−β}} .

Choosing β < α gives the result.

5. Proof of Theorem 4.

For the sake of simplicity, let us suppose a is squarefree. The proof needs slight modification otherwise. The condition

a^{p−1/d} ≡ 1( mod p)

implies that p splits completely in the field ℚ(exp(2π\sqrt{−1}/d), a^{1/d}). The number of such primes p ≤ x is easily calculated by the standard methods of analytic number theory (see for example [7] or [9]). Denoting π_{d}(x) to be the number of such primes, we find assuming the generalised Riemann hypothesis:

π_{d}(x) = \frac{li x}{dϕ(d)} + O(x^{1/2} log dx).

Hence, if d = p − 1/f(p) ≥ ϵ(x), then the number of primes p ≤ x for which this can happen cannot exceed

∑_{ϵ(x)≤d≤x^{1/2}/ log^{5} x}\{\frac{li x}{dϕ(d)} + O(x^{1/2} log dx)\} + O(x/ log^{2} x)

the latter term coming from the number of primes for which f(p) < p^{1/2}/ log^{5} p. Since the series

∑_{d=1}^{∞} \frac{1}{dϕ(d)}

converges, the result is now immediate.

Acknowledgement. The second author would like to thank the Institute for Advanced Study for its hospitality where this work was completed.

REFERENCES

[1] E. Artin, The collected papers of Emil Artin, (S. Lang and J. Tate, Eds.) Addison-Wesley (1965).

[2] N.G. de Bruijn, On the number of positive integers ≤ x and free of prime factors > y, Nederl. Akad. Wetensch. Proc. Ser. A, 54 (1951) 50-60.

[3] P. Erdös, A generalization of a theorem of Besicovitch, J. London Math. Soc., 11 (1936) 92-98.

[4] P. Erdös, On the normal number of prime factors of p − 1 and some related questions concerning Euler’s ϕ function, Quarterly Journal of Mathematics, (Oxford Ser.) 6 (1935) 205-213.

[5] R. Gupta and M. Ram Murty, Primitive points on elliptic curves, Compositio Math., 58 (1986) 13-44.

[6] H. Halberstam and H. Richert, Sieve Methods, Academic Press, London, 1974.

[7] C. Hooley, Applications of sieve methods, Cambridge University, 1976.

[8] M. Ram Murty, On Artin’s conjecture, Journal of Number Theory, 16 (1983) 147-168.

[9] M. Ram Murty, V. Kumar Murty and N. Saradha, Modular forms and the Chebotarev density theorem, American Journal of Mathematics, 110 (1988) 253 - 281.

[10] M. Ram Murty and N. Saradha, On the sieve of Eratosthenes, Canadian Journal of Mathematics, 39 (5) 1987, p. 1107 - 1122.

[11] M. Ram Murty and S. Srinivasan, Some remarks on Artin’s conjecture, Canad. Math. Bulletin, 30 (1) (1987) 80-85.

Hungarian Academy of Sciences, Budapest, Hungary Queen’s University, Kingston, Ontario, K7L 3N6, Canada