Let $n$ be a positive integer and $\mathrm{ord}_{n}(a)$ be the least positive integer $d$ such that $n\mid a^{d}-1$. I wanted to know if for some choice of $y=y(x)$, one can obtain asymptotics for the sum $$f(x,y):=\sum_{a\le y}\sum_{\substack{n\le x\\ \gcd(n,a)=1}}\frac{\gcd(n,\mathrm{ord}_n(a))}{\mathrm{ord}_n(a)}$$ where $n$ and $a$ are positive integers and $y\rightarrow\infty$ as $x\rightarrow\infty.$

  • $\begingroup$ The term in the sum depends only on $n$ and $a \bmod n$, so $f(z, n) = \Theta(z)$. Should the question be about $f(n, n)$ as a function of $n$? $\endgroup$ Nov 18, 2022 at 8:26
  • $\begingroup$ @PeterTaylor a runs over all positive integers till z and I have edited that in the question $\endgroup$ Nov 18, 2022 at 8:38
  • $\begingroup$ I assumed that already. $\endgroup$ Nov 18, 2022 at 8:41
  • 2
    $\begingroup$ Then you sum up the values of a certain $n$-periodic function, thus the asymtotics is $cz+O(1)$. Is this what you ask for? $\endgroup$ Nov 18, 2022 at 9:48
  • 2
    $\begingroup$ $$\frac{f(x,y)}{y} \approx \sum_{n \le x} \sum_{\substack{a\le n\\ \gcd(n,a)=1}}\frac{\gcd(n,\mathrm{ord}_n(a))}{\mathrm{ord}_n(a) n}$$ so you probably really want to ask about the sum on the RHS. The inner sum has an upper bound of $\frac12$ achieved when $n$ is a power of $2$ or $3$; if it has a lower bound then it's probably something like $\Theta(n^{-1 - \varepsilon})$ $\endgroup$ Nov 18, 2022 at 13:10


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.