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?
Finding coprimes closest to a certain target
algorithms;primes