Bounding sums of residue classes

Question

Is there a sharper bound for the following sum $$S:=\sum_{d \in (Z/qZ)^{*}} \overline{d},$$ where $\overline{d}$ is the inverse of $d$ modulo $q>0$? Thanks in advance.

Answer 1

Define $Q=\{d^{-1}|d\in (\mathbb{Z}/q\mathbb{Z})^{\times}\}$ now if $a\in Q$ then $a\equiv b^{-1} \text{ mod }q$ for some $b$ coprime to $q$ in addition by Euler's theorem we know that: $a\equiv b^{-1}\equiv b^{\phi(a)-1} \text{ mod } q$ so that we get:

$$\gcd(a,q)=\gcd(b^{-1},q)=\gcd(b^{\phi(a)-1},q)=1$$

Since $\gcd(x,q)=\gcd(y,q)$ if $x\equiv y \text{ mod } q$ and since if $\gcd(b,q)=1$ then $\gcd(b^{\phi(a)-1},q)=1$. Thus if $a\in Q$ then $\gcd(a,q)=1$ further if we take any two distinct integers $a,b\in (\mathbb{Z}/q\mathbb{Z})^{\times}$ we see that $a^{-1}$ and $b^{-1}$ are distinct integers modulo $q$ for if they weren't we would have: $$a^{-1}\equiv b^{-1} \text{ mod } q\implies (ab)a^{-1}\equiv(ab)b^{-1} \text{ mod } q\implies b\equiv a \text{ mod } q$$ Contradicting our initial assumption that $a$ and $b$ were distinct modulo $q$, thus we know that $Q$ contains $\phi(q)$ distinct elements less then or equal to $q$ and coprime to $q$ proving $Q=(\mathbb{Z}/q\mathbb{Z})^{\times}$.

From this we can write:

$$S:=\sum_{d \in (Z/qZ)^{*}} \overline{d},=\sum_{d \in (Z/qZ)^{*}}d=\sum_{\substack{d\leq q \\ (d,q)=1}}d=\sum_{d\mid q}\mu(d)d\big(\sum_{n\leq q/d}n\big)=\frac{1}{2}\sum_{d\mid q}\mu(d)d\big(\frac{q^2}{d^2}+\frac{q}{d})$$ $$=\frac{q}{2}\big(\sum_{d\mid q}\mu(d)\frac{q}{d}+\sum_{d\mid q}\mu(d)\big)=\frac{q}{2}(\phi(q)+\delta_{q,1})$$

So that for all integers $q>1$ we can simplify your sum as:

$$\frac{q}{2}\phi(q)=\sum_{d \in (Z/qZ)^{*}} \overline{d},$$