A Study on Gaps between Integers Having a Common Divisor with an Odd Semiprime - Xingbo Wang (Mathematics and Computer Science: Research Updates Vol. 4, 2025)
This paper elucidates the distribution law of integers that share a common divisor with an odd semiprime N = pq, where p and q are odd primes satisfying \(λ\)p < q < (\(λ\)+1)p, and \(λ\) is a positive integer. It demonstrates that within the interval [1,N-1], the gaps between multiples of p or q exhibit symmetric behavior ranging from 0 to p - 1. Specifically, each gap from 0 to p - 2 appears exactly twice in a symmetric manner, while the gap p - 1 occurs precisely q - p - 1 times across p distinct subintervals. Among these p subintervals, q - \(λ\)p - 1 subintervals each contain \(λ\) gaps of size p - 1, while the remaining subintervals each contain \(λ\) - 1 gaps of size p - 1. From a positional perspective, there are either \(λ\) or \(λ\) + 1 multiples of p between two adjacent multiples of q, with exactly \(λ\) multiples of p appearing both before the first multiple of q and after the last multiple of q. These findings can significantly facilitate the design of algorithms for identifying the divisors of unfactorized composite integers.