On the order of \((a \text{mod} p)\). (English) Zbl 0931.11034

Erdős, Pál; Murty, M. Ram

Gupta, Rajiv (ed.) et al., Number theory. Fifth conference of the Canadian Number Theory Association, Ottawa, Ontario, Canada, August 17–22, 1996. Providence, RI: American Mathematical Society. CRM Proc. Lect. Notes. 19, 87-97 (1999).

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\pmod p\). In the present paper the authors 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)\) primes \(p\leq x\)). On noticing that if \(f(p)< z\), then \(p\) divides the product \(\prod_{t<z} (a^t-1)\), one easily sees that \(f(p)> \sqrt{p}/\log p\) for almost all primes. The authors sharpen this as follows: if \(\varepsilon(p)\) is any function tending to zero as \(p\to\infty\), then for almost all primes \(f(p)\geq p^{1/(2+ \varepsilon(p))}\). This result is a consequence of the trivial lower bound \(f(p)> \sqrt{p}/ \log p\) and the following result (with \(\delta= 1/2\)). Let \(\delta> 0\) and fixed. Let \(\varepsilon(x)\) be any function tending to zero as \(x\to\infty\). The number of primes \(p\leq x\) such that \(p-1\) has a divisor in the interval \(I= (x^\delta, x^{\delta+ \varepsilon(x)})\) is \(o(x/\log x)\). This result can be viewed as the \(p-1\) analogue of a theorem of Erdős to the extent that the number of integers \(n\leq x\) having a divisor in the interval \((x^\delta, x^{\delta+ \varepsilon(x)})\) is \(o(x)\) [P. Erdős, J. Lond. Math. Soc. 11, 92-98 (1936; Zbl 0014.01104)] and indeed, the proof closely follows the proof of the latter result. By an alternative method the authors prove a variant of their main result in which the estimate for the exceptional set is sharper than \(o(x/\log x)\). It is also shown (by an easy argument) that if one assumes the generalized Riemann hypothesis, then \(f(p)\geq p/\varepsilon (p)\) for almost all primes \(p\). Furthermore, the authors state a rank \(r\) version of their results.
The reader might be surprised to see Pál Erdős mentioned as one of the authors of the present paper. This is explained in a footnote: ‘This paper was written by the authors in 1987 while Pál Erdős was visiting McGill. We had planned to work on an expanded version refining Theorem 2 but neither of the authors found the time or the opportunity to continue the work. Unfortunately, Pál has passed away. It is published here in the hope that others may continue the task’.
For the entire collection see [Zbl 0910.00037].

Reviewer: Pieter Moree (Berkel EN Radeivrijs)

MSC:

11N37	Asymptotic results on arithmetic functions
11A07	Congruences; primitive roots; residue systems
11N35	Sieves

Keywords:

order; rank; Brun’s sieve

Citations:

Zbl 0014.01104