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


How to Cite

Wang, Xingbo. 2024. “Maximum Gap Among Integers Having a Common Divisor With an Odd Semi-Prime”. Journal of Advances in Mathematics and Computer Science 39 (10):51-61. https://doi.org/10.9734/jamcs/2024/v39i101934.