1
$\begingroup$

Let $n$, $r$ be integers such that $n\geq 2$ and $2 \leq r \leq n$. Recall that the Euler's totient function $\varphi(n)$ is equal to the number of integers $<n$ that are coprime to $n$. Now I want to generalize this quantity and define $\psi(n,r)$ as the number of integers $<r$ that are coprime to $n$. Note that by definition $\psi(n,n)=\varphi(n)$. I am interested in obtaining a good lower bound on $\psi(n,r)$ in general for all $r$, as well as in the special case when $r \approx \varphi(n)/2$. In the latter case, $r = r(n)$ is just a function of $n$, so it would be interesting to determine the rate of growth of the function $\psi(n,r(n))$ as $n$ approaches infinity.

In the very special case when $n=p^k$ is a prime power, it is easy to prove that

$$ \psi(p^k,r) = r - \lfloor r/p\rfloor. $$

But how do we expand this result to $n$ with several distinct prime factors?

In general, what do we know about the distribution of integers coprime to $n$ on the interval $[1,n-1]$ when $n$ is large and has many prime factors? Has this question been studied at all? I'd be thankful for any references.

$\endgroup$
2
  • $\begingroup$ So much to say. So little time. Gerhard "See Questions 37679 And 88777" Paseman, 2017.02.10. $\endgroup$ Commented Feb 11, 2017 at 5:26
  • $\begingroup$ mathoverflow.net/questions/22953/… looks to be essentially the same question $\endgroup$ Commented Feb 11, 2017 at 8:44

0

Browse other questions tagged .