I wanted to know if we know any asymptotic formula/bound for the following sum

$$ \sum_{1 \leq a < n \\(a,n) = 1 } \phi(a) \ .$$

A trivial upper bound could be $$ \sum_{a=1}^{n} \phi(a) = \frac{3}{\pi^2} n^2 + O(n^{1+\epsilon}), $$ but I wanted to know if we could do better than that. Thanks in advance for the help!



  • $\begingroup$ You might enjoy working with the complementary sum, where a is 1 or a is not coprime to n. Gerhard "See If It Helps Any" Paseman, 2017.08.13. $\endgroup$ Aug 13, 2017 at 20:05
  • $\begingroup$ OEIS sequence A053570. $\endgroup$ Aug 13, 2017 at 23:02

1 Answer 1


The answer here is

$$\frac{3}{\pi^2}n^2\prod_{p\mid n} \frac{p}{p+1}+O(nd(n)\log\log n+ n\log n),$$

where $d(n)$ is a divisor function and product is over prime values of $p$.

To prove this, note first that

$$\sum_{\substack{a\leq n \\ (a,n)=1}} \varphi(a)=\sum_{a \leq n} \varphi(a)\sum_{d \mid (a,n)} \mu(d)=\sum_{d \mid n} \mu(d)\sum_{bd\leq n} \varphi(bd).$$

Now, using the identity

$$\varphi(a)=a\sum_{d \mid a}\frac{\mu(d)}{d}$$

we get

$$\sum_{bd \leq n} \varphi(bd)=\sum_{b \leq \frac{n}{d}}bd\sum_{c\mid bd} \frac{\mu(c)}{c}.$$

Changing order of summation, we obtain

$$\sum_{bd \leq n}\varphi(bd)=d\sum_{c \leq n}\frac{\mu(c)}{c}\sum_{\substack{b \leq n/d \\ \frac{c}{(c,d)} \mid b}}b.$$

As for any $x$ and $y$ the equality

$$\sum_{\substack{b \leq x \\ y \mid b}} b=\frac{x^2}{2y}+O(x)$$

holds, the inner sum equals

$$\sum_{\substack{b \leq n/d \\ \frac{c}{(c,d)} \mid b}}b=\frac{n^2(c,d)}{2cd^2}+O(\frac{n}{d}).$$


$$\sum_{bd \leq n} \varphi(bd)=\frac{n^2}{d}\sum_{c \leq n} \frac{\mu(c)(c,d)}{2c^2}+O(n\log n).$$

Let us now compute the sum in the RHS of this identity:

$$\sum_{c \leq n} \frac{\mu(c)(c,d)}{c^2}=\sum_{c=1}^{+\infty} \frac{\mu(c)(c,d)}{c^2}-\sum_{c>n} \frac{\mu(c)(c,d)}{c^2}=S_1-S_2$$

(both series are obviously convergent) Now we should compute $S_1$ and estimate $S_2$. Note that the function $\frac{\mu(c)(c,d)}{c^2}$ is multiplicative due to the multiplicativity of $\mu(c), c^2$ and $(c,d)$. Thus,

$$S_1=\prod_p (1-\frac{(c,p)}{p^2})=\prod_p (1-1/p^2)\prod_{p \mid d}\frac{p}{p+1}=\frac{6}{\pi^2}\prod_{p \mid d} \frac{p}{p+1}.$$

To obtain the estimate for the $S_2$, observe that

$$|S_2|\leq \sum_{c>n} \frac{(c,d)}{c^2}\leq \sum_{t \mid d} \sum_{ft>n} \frac{t}{(ft)^2}=O\left(\frac{d(n)}{n}\right).$$


$$\sum_{bd \leq n} \varphi(bd)=\frac{3n^2}{\pi^2d}\prod_{p \mid d} \frac{p}{p+1}+O(nd(n)/d+n\log n).$$

Summing this over all $d$, we finally get

$$\sum_{\substack{a\leq n \\ (a,n)=1}} \varphi(a)=\frac{3n^2}{\pi^2}\sum_{d \mid n} \frac{\mu(d)}{d}\prod_{p \mid d} \frac{p}{p+1}+O(nd(n)\log\log n+n\log n)=\frac{3n^2}{\pi^2}f(n)+O(nd(n)\log\log n+\log n).$$

To get a bit more closed-form expression for $f(n)$ note that $f$ is again multiplicative and for any prime $p$ and positive $\alpha$ we have



$$f(n)=\prod_{p \mid n} \frac{p}{p+1},$$

as needed.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .