I would like to use something along the lines of the fact that for sufficiently large n there is always a number $1<m<n$ that is coprime to n so that $m<n^3/2$. (In other words, this is clearly true if n is odd, or if it is not a multiple of 6, or not a multiple of 30, etc...) This seems like it is certainly true and in the literature but I cannot find an easy proof or an easy reference, Does anyone know one?
2026-05-03 19:24:09.1777836249
Number with small non-divisors
45 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
OEIS A002110 lists the primorials, the product of the first $p$ primes. They begin, as you have noted, $$1, 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870,\ldots$$ and clearly grow quite quickly. There is a note that for the $p^{th}$ prime they are approximately $p^p$, so the last of these is the ninth one and $9^9=387420489,$ which is of the same order. The tenth prime, $29$, will not divide this. This is tiny compared with the primorial. We can say that every number smaller than $223092870$ is coprime to one of the primes less than or equal to $23$.
Your problem comes at the low end. Presumably you are prohibiting $1$ for $m$, and when $n$ is $6$ the only other coprime number is $5$, which is not much smaller. Already by $30$ we have $7$ being coprime. It would be common to make the statement in the form: for all $n \gt$ something, there is an $m\gt 1$ and less than $f(n)$ that is coprime to $n$. $f(n)$ can grow very slowly. The higher you make the lower limit, the smaller it can be.
As an example, you could say that for $n \gt 30$ there is an $m \gt 1$ and $\lt 2 \log n$ that is coprime to $n$. I think the constant can come down as the lower limit gets higher. You can probably get a function that grows more slowly than $\log n$ as well.