A Study on Gaps between Integers Having a Common Divisor with an Odd Semiprime

Abstract

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 \(\lambda\)p < q < (\(\lambda\)+1)p, and \(\lambda\) 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 - \(\lambda\)p - 1 subintervals each contain \(\lambda\) gaps of size p - 1, while the remaining subintervals each contain \(\lambda\) - 1 gaps of size p - 1. From a positional perspective, there are either \(\lambda\) or \(\lambda\) + 1 multiples of p between two adjacent multiples of q, with exactly \(\lambda\) 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.