Least number coprime to a given integer

Question

For a positive integer $n$ let $$f(n):=\min\{m\in \mathbb N: m>1, \gcd(m,n)=1\} .$$ Equivalently, $f(n) $ is the smallest prime not dividing $n$. Is there any upper bound literature for this? It is not difficult to prove that $$ \#\{1<m\leq x: \gcd(m,n)=1 \} \geq \frac{\phi(n) }{n } x-1-2^{\omega(n) }, $$ hence, $$f(n) \leq 2 + 2^{\omega(n) }\frac{n }{\phi(n) }\leq 2+ 4^{\omega(n ) } .$$ If $n=\prod_{p\leq t}p$ then $f(n) \asymp t \asymp \omega(n) \log \omega(n)$, so perhaps something polynomial in $\omega(n)$ might be achievable for general $n$. Is it possible to improve this as function of $\omega$? PS. I do not care about bounds without $\omega$, since these are easy. For example, all primes $p<f(n)$ must divide $n$ hence $$ \prod_{p<f(n) } p \leq n \Rightarrow f(n) \ll \log n.$$

Answer 1

If $f(n) = p_{m+1}$ is the $(m+1)$-th prime, then $n$ must be divisible by $p_1 \cdots p_m$, hence $f(n) \ll m \log m \ll \omega(n) \log \omega(n)$. Your example shows one cannot hope for a better bound.

Answer 2

Let $f(n)$ be the least prime not dividing $n$. If $p_k$ is the $k$-th prime, $m\geq 1$ is an integer, and $$q_m = \prod_{k=1}^m p_k,$$ then $f(q_m)=p_{m+1}$. Indeed, $q_m$ is the least positive integer at which $f$ equals $p_{m+1}$, so we find that $f$ is maximized along the sequence of primorials $q_m$.

By the prime number theorem, we have $$q_m = e^{(1+o(1))m\log m},\qquad p_{m+1}=(1+o(1))m\log m.$$ Thus, $$f(e^{(1+o(1))m\log m})=(1+o(1))m\log m.$$ Inverting this relationship, we find that $$f(n) = (1+o(1))\log n$$ when $n$ is a primorial. Since $f$ is maximized along the primorials, we find that $$f(n)\leq (1+o(1))\log n$$ for all $n\geq 2$. Using explicit forms of the prime number theorem, one could bound the $o(1)$ term completely explicitly.