Maximum Gap among Integers Having a Common Divisor with an Odd Semi-prime
Xingbo Wang *
Guangzhou College of Applied Science and Technology, Guangzhou City, PRC, 511370, Foshan University, Foshan City, PRC, 528000, China.
*Author to whom correspondence should be addressed.
Abstract
For an odd semi-prime N = pq with p < q < 2p, this paper demonstrates that the maximum gap between two integers sharing a common divisor with N is p - 1. Within interval [1, N - 1] there exists a sequence of such gaps that can be periodically grouped into small clusters determined by the quotient of p divided by q - p. Furthermore, the total number of the terms in the sequence is an odd number no smaller than 1. These findings illustrate that the large gaps among multiples of the divisors of a composite odd integer are distributed sparely and periodically. Such distribution is advantageous for designing randomized algorithms capable of identifying a divisor of a composite odd integer within a limited range.
Keywords: Integer distribution, semi-prime, common divisor, algorithm design