This is tightly related to the Jacobsthal function defined to be the smallest integer $j(n)$ such that any segment of $j(n)$ consecutive integers contains an integer co-prime with $n$. Iwaniec ("On the problem of Jacobsthal", Demonstratio Math. 11, 225–231, 1978) proved that $j(n)=O(\log^2(n))$; this implies your statement.
Seva
- 23k
- 2
- 59
- 141