# Asymptotics for a sum involving GCD and multiplicative order

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.$$

• 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$? Nov 18, 2022 at 8:26
• @PeterTaylor a runs over all positive integers till z and I have edited that in the question Nov 18, 2022 at 8:38
• I assumed that already. Nov 18, 2022 at 8:41
• 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? Nov 18, 2022 at 9:48
• $$\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})$ Nov 18, 2022 at 13:10