Finding the first number larger than N that is a relative prime to M

Question

Basically, the title says everything. The numbers are not too big (the maximum for N is ~2/3 * max(long) and max M is max(long)), so I think even a simple solution that I currently have is sufficient. M is always bigger than N.

What I currently have:

• Most simple, just start from N + 1, perform plain Euclidean GCD, and if it returns 1 we are done, if not increment and try again.

I would like to know what is the worst case scenario with this solution. Performance is not a big issue, but still I feel like there must be a better way.

Thanks.

About the worst case, I made a small test:

Random r = new Random();
while (true)
            {
                long num = (long) r.Next();
                num *= r.Next();
                f((long)(num * 0.61), num);
            }

...

public static int max;

        public static int f(long N, long M)
        {
            int iter = 0;
            while (GCD(N++, M) != 1)
            {
                iter++;
            }

            if (iter > max)
            {
                max = iter;
                Console.WriteLine(max);
            }

            return 0;
        }

It is running for ~30 minutes and the worst case so far is 29 iterations. So I believe that there is a more precise answer then O(N).

Answer 1

I don't know the worst scenario, but using the fact that M < 2⁶⁴, I can bound it above by 292 iterations and below by 53 (removing the restriction that the ratio N/M be approximately fixed).

Let p₁, …, p_k be the primes greater than or equal to 5 by which M is divisible. Let N' ≥ N be the least integer such that N' = 1 mod 6 or N' = 5 mod 6. For each i = 1, …, k, the prime p_i divides at most ceil(49/p_i) of the integers N', N' + 6, N' + 12, …, N' + 288. An upper bound on ∑_i=1,…,k ceil(49/p_i) is ∑_i=3,…,16 ceil(49/q_i) = 48, where q is the primes in order starting with q₁ = 2. (This follows because ∏_i=3,…,17 ≥ 2⁶⁴ implies that M is the product of at most 14 distinct primes other than 2 and 3.) We conclude that at least one of the integers mentioned is relatively prime to M.

For the lower bound, let M = 614889782588491410 (product of the first fifteen primes) and let N = 1. After 1, the first integer relatively prime to the first fifteen primes is the sixteenth prime, 53.

I expect both bounds could be improved without too much work, though it's not clear to me for what purpose. For the upper bound, handle separately the case where 2 and 3 are both divisors of M, as then M can be the product of at most thirteen other primes. For the lower bound, one could try to find a good M by running the sieve of Eratosthenes to compute, for a range of integers, the list of primes dividing those integers. Then sweep a window across the range; if the product of the distinct primes in the window is too large, advance the trailing end of the window; otherwise, advance the leading end.