On the Order of $a$ modulo $n$ on Average

Abstract

Let $a>1$ be an integer. Denote by $l_a(n)$ the multiplicative order of $a$ modulo integer $n\ge 1$. We prove that there is a positive constant $\delta$ such that if $x^{1-\delta }{\log }^{3}x=o(y)$, then $$\frac{1}{y}\sum _{a<y}\frac{1}{x}\sum _{\begin{array}{c}a<n<x\\ (a,n)=1\end{array}}{l}_a(n)=\frac{x}{\log x}\exp \left(B\frac{\log \log x}{\log \log \log x}(1+o(1))\right)$$ where $$B=e^{-\gamma }\prod _p\left(1-\frac{1}{(p-1{)}^2(p+1)}\right).$$ This is an improvement over a statement in Kurlberg and Pomerance (see ~\cite{KP}): $$\frac{1}{x^2}\sum _{a<x}\sum _{a<n<x}{l}_a(n)=\frac{x}{\log x}\exp \left(B\frac{\log \log x}{\log \log \log x}(1+o(1))\right).$$

References in corpus (1)

• On the period of the linear congruential and power generators

Cited by in corpus (1)

• Average Results on the Order of $a$ modulo $p$