Intervals of Length O(k²/(log log k)²) Contain a Number Coprime to the Modulus

For a modulus with at most (k) distinct prime factors, the manuscript claims that an interval of length at most (Ck^2/(\log\log 3k)^2) is sufficient to guarantee an integer coprime to the modulus, for an absolute constant (C). The same constant works for every such modulus and every starting point, including negative ones. The manuscript does not specify a numerical value for (C).^†

The motivating example is 30. Crossing out integers divisible by 2, 3, or 5 blocks 2 through 6; 7 is coprime to 30. The longest blocked run is five, so every six consecutive integers include an escape. Jacobsthal’s function asks how long such a blocked run can be in general. The claim here bounds the interval length needed to guarantee an escape, regardless of which primes divide the modulus.

Repeated prime factors do not change the problem: only the distinct primes matter. Nor does moving the interval create a fundamentally different case. The proof allows each prime to forbid any one remainder, rather than just remainder zero. For example, the forbidden remainders 1 modulo 2, 0 modulo 3, and 2 modulo 5 are all realized by 27. By the Chinese remainder theorem, a shift with the required remainders exists for any finite set of primes. Thus arbitrary translations of the original coprimality problem can be treated as arbitrary forbidden residue classes.

A small example shows why the proof tracks overlaps carefully. In the integers 1 through 15, removing the multiples of 2 leaves eight numbers. To remove numbers divisible by 3 or 5 without double-counting 15, assign each rejected number to its smallest prime divisor among those still being considered. The prime 3 owns 3, 9, and 15; 5 owns 5. Four numbers survive: 1, 7, 11, and 13.

That partition can be repeated inside the buckets. Among the odd multiples of 5, there are two candidates, 5 and 15; the latter also belongs to the 3-bucket. Their exact contribution is therefore (2-1), giving the count (8-3-2+1). In the general expansion, paths through decreasing primes contribute with alternating signs.

The proof does not expand every path indefinitely. It controls which branches enter the expansion: even levels give lower bounds, odd levels give upper bounds, and a stopping rule keeps exact counts on selected even branches. This balance matters later, because the proof’s comparison of stopped branches works in aggregate—not necessarily at each stop individually.

The manuscript’s main technical engine is a counting theorem. For all primes up to a sufficiently large cutoff (z), and for every assignment of one forbidden remainder to each prime, it guarantees many survivors among the integers from 1 to (Y), where (Y) is the integer part of (z^2/(\log z)^2). Its lower bound is expressed using (V_0), the density associated with the small primes up to (w), and (B), which measures the logarithmic gap between (w) and (z). With the displayed choices, the guaranteed count is comparable to (Y\log\log z/(\log z)^2).

Obtaining a positive guarantee is the difficult part. At the critical sieve parameter 2, the usual leading lower estimate vanishes: that does not mean there are no survivors, but it gives no positive lower bound. The proof retains a smaller boundary contribution in a reference tree and compares it with the actual residue-class counts. It groups prime paths into regular boxes, associates a finite list of rational numbers with each candidate box, and controls discrepancies except on an exceptional set of bounded harmonic weight. Variance estimates isolate the difficult cases; carefully chosen even stopping points capture most of their path weight so exact counts can be compared by averaging.

These are technical estimates, not consequences of the toy examples. In the final accounting, the reference contribution is at least (c_LR). The retained errors cost at most three-eighths of that amount, while the total stopped correction is non-negative. At least five-eighths of the positive margin therefore remains. That establishes the survivor theorem once the preceding estimates are in place.

The theorem initially handles primes only up to (z). A modulus may also have larger prime factors, each of which could remove some of the survivors. Put (X=Y/z). Within a progression belonging to a prime (q>z), the manuscript uses an upper-sieve bound to limit the number of deleted survivors to a constant times ((1+X)/\log X). This improves on simply counting at most (1+X) positions. There are at most (k) such remaining prime factors, so their combined deletion is at most (k) times that bound, including when a prime exceeds the interval’s length.

Now choose (z=A k\log k/\log\log k), with (A) a sufficiently large fixed constant. The survivor lower bound grows quadratically in (A), while the upper bound on deletions grows linearly in (A), apart from a lower-order term. Taking (A) large enough leaves at least one survivor. Since (Y) is on the scale of (z^2/(\log z)^2), this choice yields an interval length on the scale of (k^2/(\log\log k)^2), giving the claimed quadratic bound.

The argument first applies for sufficiently large (k). For the finitely many smaller values, the manuscript invokes an elementary inclusion-exclusion bound and enlarges (C) to cover them. The result is uniform over prime sets; it is not a claim that the first (k) primes are the only relevant case. Nor does it determine the optimal growth of Jacobsthal’s function. The examples verify particular constructions, not the full theorem.