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

I am not sure if this question is best suited for math exchange. I already tried on stackoverflow without any luck, so I hope that your bright minds will be more helpful.

So, basically the tile says everything. The numbers are not too big (so, this probably is not very interesting for the regular crowd here :)). The maximum for M is 2 * 10 ^ 63 and N is ~0.61 * M.

I made a small program for testing purposes that starts from N + 1, performs a simple Euclidean GCD, and if numbers are not relative primes we increment N.

I would like to know, is there any better solution. This looks very trivial, and maybe will be fast enough, but I would like to know is there anything better.

Also, if an answer for aforementioned question is No, I would like to know what is the worst case for the given algorithm.

I ran a test that will perform the above-described algorithm on some random numbers, and so far the result is always found in the less than 30 iterations.

Thanks.

-
To the contrary, I think the question fits perfectly here. One question: Do you really want the literal first number larger than $N$ (relatively prime to $M$, of course), or do you just want a fast way of finding something relatively prime to $M$ and not much more than $N$? – Cam McLeman Feb 1 '12 at 14:09
Something 'not much more than N' would suite me just fine. – Klark Feb 1 '12 at 15:32

The number of positive integers smaller than $M$ and relatively prime to $M$ is given by Euler's totient function $\varphi(M)$. The following inequality holds for all $M>2$: $$\varphi(M)>\frac{M}{e^\gamma\log\log M+\frac{3}{\log\log M}},\quad e^\gamma=1.7810\dots$$ On average, your algorithm should find the solution in at most $e^\gamma\log\log N$ iterations.
To speed the calculations, you could find a few small primes $p$ dividing $M$, and perform the Euclidean MCD only on candidates that are not divisible by those primes. For instance, if $M$ is even, you should try only odd candidates. This will be most helpful if you have to do the computations for a fixed $M$ and many different $N$'s.
@TonyK That the expected value of the number of iterations needed is $e^\gamma\log\log N$, that is, between $N+1$ and $N+e^\gamma\log\log N$, unless you are unlucky, there should be an integer relatively prime to $M$. This is a heuristic and probabilistic argument. – Julián Aguirre Feb 1 '12 at 17:30