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.