Minimal Gap among Integers having a Common Divisor with an Odd Semi-prime
Xingbo Wang *
Guangzhou College of Applied Science and Technology, Guangzhou City, 511370 and Foshan University, Foshan City, 528000, PRC, China.
*Author to whom correspondence should be addressed.
Abstract
For an odd semi-prime N = pq, this paper proves that the gaps are symmetrically distributed between two integers in interval [1,N - 1] that have a common divisor with N and there exists a gap of zero between a multiple of p and a multiple of q. These results exhibit that the multiples of the divisors of a composite odd integer lie accumulatively here and there although each of them lies sparsely in a whole interval. Such distribution of local accumulation in global sparsity is beneficial for designing randomized algorithms that can find a divisor of a composite odd integer. The paper also leaves a problem to find out the detail distribution of the non-zero gaps.
Keywords: Integer distribution, gap, semi-prime, common divisor, algorithm design