Estimating the number of integers less than $m$ that are relatively prime to $p_n\#$

Question

Let $m \ge 2$ be an integer.

Let $p_n$ be the $n$th prime so that $p_1 = 2, p_2 = 3,$ etc.

Let $p_n\#$ be the primorial for $p_n$.

Let $\gcd(a,b)$ be the greatest common divisor for $a$ and $b$.

Let $f(m,p_n) =$ the number of integers $x$ where $0 < x \le m$ and $\gcd(x,p_n\#)=1$

For example:

• $f(10,2)=5$
• $f(10,3)=3$

It seems to me that $f(m,p_n)$ can be estimated in the following way:

$$\left\lfloor\left(\prod\limits_{p_i \le p_n}\frac{p_i-1}{p_i}\right)m\right\rfloor \le f(m,p_n) \le \left\lceil\left(\prod\limits_{p_i \le p_n}\frac{p_i-1}{p_i}\right)m\right\rceil$$

Here's my argument:

For any $m$:

• at least $\left\lfloor\frac{m}{2}\right\rfloor$ are odd
• at least $\left\lfloor\left(\frac{2}{3}\right)\left(\frac{m}{2}\right)\right\rfloor$ are odd and not divisible by $3$,
• at least $\left\lfloor\left(\frac{4}{5}\right)\left(\frac{2}{3}\right)\left(\frac{m}{2}\right)\right\rfloor$ are odd, not divisible by $3$ and not divisible by $5$.
• and so on.
• at most $\left\lceil\frac{m}{2}\right\rceil$ are odd.
• and so on in the same way.

Is my reasoning valid? If yes, what is the standard argument? If my reasoning is not valid, could you provide a counter example?

Answer 1

This is correct, you are basically applying inclusion-exclusion formula. There are at least two kind of generalizations of the problem you mentioned above:

1. Given pairwise coprime positive integers $a_1,\ldots,a_k$, then the number of positive integers $n\le x$ coprime with each $a_i$ admits asymptotic density $$ \left(1-\frac{1}{a_1}\right)\cdots \left(1-\frac{1}{a_k}\right). $$

2. Given positive integers $a_1,\ldots,a_k$, then the number of positive integers $n\le x$ not divisible by each $a_i$ admits asymptotic density $$ \ge \left(1-\frac{1}{a_1}\right)\cdots \left(1-\frac{1}{a_k}\right). $$ For a proof see here and a textbook exposition here.