Finding coprimes closest to a certain target

Question

Given an input $m$, I am trying to find an algorithm that will give me the number $p$ that is closest to $\tfrac47 m$ and co-prime with $m$.

Where $m$ is odd, I have no problem producing an outcome close to the target, simply by squaring $2$ until close enough to the target.

When $m$ is even, I have a bit more trouble. I have tried a few different methods with no success. I have tried starting with $p = 3$, then multiplied $p\cdot\mathrm{gcd}(p-1, m)$ until $p$ and $m$ share all factors (in other words, until $\mathrm{gcd}(p-1, m) = 1$). This eventually finds a coprime, but there is no guarantee that it is close to the target, and I'm not sure how to operate on the number from here to get another coprime closer to the target.

The algorithm needs to be able to handle massive numbers with hundreds of digits, so it needs to be pretty efficient.

I'm not sure if I'm missing a necessary fact about coprime numbers, or if I'm just misinterpreting the info I have. Can anyone point me in the right direction? Maybe a fact about coprime numbers that I'm missing?

Answer 1

If you want the truely closest coprime to $\frac 4 7m$, you could start with $n = \mathrm{round}(\frac 4 7m)$. Then, while $\gcd(n,m) \neq 1$, try again with $n$ being the closest number to $\frac 4 7 m$ such that $n - q \not \equiv 0 \mod \gcd(q,m)$ for any previously checked number $q$ (keep track of previously checked numbers and gcds in a list)

Checking one candidate has complexity $\mathcal O(\log(m))$. The probability of any two numbers being coprime is $\frac 6 {\pi^2} \approx 60\%$ so the numbers of candidates to check should be $\mathcal O(1)$ on average.

Overall this should find you the closest coprime in $\mathcal O(\log(m))$ operations.

Answer 2

Let m = 7i + j, 0 ≤ j < 7. Let p = 4i + k for some small k. When we calculate gcd (p, m) we get the following pairs:

7i + j, 4i + k // subtract right hand side from left and exchange
4i + k, 3i + j - k // subtract right hand side from left and exchange
3i + j - k, i + 2k - j // subtract 3x right hand side
i + 2k - j, 4j - 7k

so we need gcd (m, 4j - 7k) = 1. i and j are fixed. Check values k in the right order (the order is 0, 1, -1, 2, -2, 3, -3, 4, except you swap each pair if j ≥ 4). Ignore k where 4j - 7k = 0. For each k find the prime factors of 4j - 7k and check if m has any of these factors. If there are no common prime factors you found p = 4· i + k.

To make the search faster, you would collect as many prime factors as possible with a product P, as long as gcd (m, P) can be calculated quickly.

Worst case is when m has all the prime factors of 4j - 7k for many consecutive values k, but the number of different prime factors that a number m can have is quite limited, something like $\log m / \log \log m$