# Interesting question about Euler's Phi function

We have that $\phi(n)$ is the number of positive integers less than $n$ and relatively prime to $n$.

I tried to extend this definition by working with $\phi_x(n)$, which is the number of positive integer less than $x$ and relatively prime to $n$. I wonder if there was a research about this extension before, because I found a very interesting inequality. (haven't proved yet, but I checked for some value of $m,n$)

Let $m,n$ be positive integers. Then we have:

$\phi(1)+\phi(2)+\cdots+\phi(m)+\phi_n(1)+\phi_n(2)+\cdots+\phi_n(m) \geq \phi(n+1)+\phi(n+2)+\cdots+\phi(n+m)$

Does anyone have any hint for this or any resources related to $\phi_x(n)$? Thank you in advance.

## 2 Answers

I don't really understand the practicality of $\phi_x(n)$. What's your purpose for studying it?

In any case, note that $\phi_n(m) = \phi(m)$ if $n \geq m$. This allows us to show that your inequality is false in certain ranges. Namely, if $n \geq m$, then $\sum_{k \leq m} (\phi(k) + \phi_n(k)) = 2 \sum_{k \leq m} \phi(k) = \frac{6}{\pi^2} m^2 + O(m \log m),$ while $\sum_{n + 1 \leq k \leq n + m} \phi(k) = \frac{3}{\pi^2} (n + m)^2 + O((n + m) \log (n + m)) - \frac{3}{\pi^2} (n + 1)^2 + O((n + 1) \log (n + 1)),$ which is $\frac{3}{\pi^2} m(2n + m) + O(n \log n).$ It follows that $\sum_{n + 1 \leq k \leq n + m} \phi(k) - \sum_{k \leq m} (\phi(k) + \phi_n(k)) = \frac{3}{\pi^2} m(2n - m) + O(n \log n).$ So if $(\log n)^2 \ll m \leq n$, say, then the right-hand side is positive for all sufficiently large $n$, contradicting your inequality.

• why is $\phi_n(m) = \phi(m)$ for $n \ge m$? consider $n = 2m$. The number of integers less than $2m$ and relatively prime to $m$ is not the same as number of integers less than $m$ and relatively prime to $m$. – sku Jun 22 '17 at 14:48
• Ah, I misread.. – Peter Humphries Jun 22 '17 at 15:24

$\phi(x,n) = \sum\limits_{k \le x} \left[\frac{1}{(n,k)}\right] = \sum\limits_{k \le x} \sum\limits_{d \mid (n,k)} \mu(d) = \sum\limits_{k \le x} \sum\limits_{d \mid n, d\mid k} \mu(d)$

For a fixed divisor $d$ of $n$, we sum over all $k$ in the range $1 \le k \le x$ which are multiples of $d$. We can write $k = qd$, then $1 \le k \le n$ only if $1 \le q \le \left[\frac{x}{d}\right]$

Hence $\phi(x,n) = \sum\limits_{d \mid n} \sum\limits_{q = 1}^{[x/d]} \mu(d) =\sum\limits_{d \mid n} \mu(d) \sum\limits_{q = 1}^{[x/d]} 1 = \sum\limits_{d \mid n} \mu(d) \left[\frac{x}{d}\right]$

This looks correct as $\phi(n,n) = \sum\limits_{d \mid n} \mu(d) \left[\frac{n}{d}\right] = \sum\limits_{d \mid n} \mu(d) \frac{n}{d} = \phi(n)$