# Proof that if a natural number is coprime to two other natural numbers than there is another coprime natural number within a given range.

Let $$n$$, $$m$$, and $$c$$ be distinct natural numbers such that $$1 < n < m$$ and $$c$$ is coprime to both $$n$$ and $$m$$.

Show that there is a natural number $$d$$ coprime to both $$n$$ and $$m$$ such that $$c < d \leq c+2m$$.

I can’t quite put my finger on how to figure out how to prove it.

I am also curious if it generalizes to any number of natural numbers all coprime to $$c$$, but I feel like that might be a bit challenging for MSE. So a proof of a generalization is not necessary if it is known to be beyond reasonable effort of an answerer.

• Coprimality to two integers $n,m$, is equivalent to coprimality to their $lcm(n,m)$. Check if this is true : If it is, prove it, and see if that simplifies the problem above. Sep 1, 2020 at 4:00
• The problem now changes : basically, you have a number $x$, and you have to show that in the list of numbers coprime to $x$, consecutive entries are not too far apart. But then again, we are not sure of that. Sep 1, 2020 at 5:06
• The problem did not change, I just rewrote it with the knowledge of what I said earlier. Note that $lcm(n,m) = x$ is the only number involved in this question, rather than two numbers $m$ and $n$. Nevertheless, I've followed your question and would love to see your answer. Sep 1, 2020 at 6:18
• Thanks for the update, it really is very nice. Sep 9, 2020 at 6:57

We prove a stronger claim. First, we may assume WLOG that $$\gcd(m,n)=1$$. This is because you can remove any prime factors dividing $$m$$ from the prime factorization of $$n$$ and the claim is unaffected, since only $$n$$ decreases, but the union of the prime factors is still the same.

Next, we show that given positive integer $$k$$, the positive integers $$km+1,km+2,\ldots,(k+1)m$$ contain a number that is relatively prime to $$m$$ and $$n$$. Write $$n=ab$$ where $$a$$ is the product of all primes (with multiplicity) dividing $$n$$ that divide $$k$$, and $$b$$ is the product of all primes dividing $$n$$ that do not divide $$k$$. Consider the number $$km+b$$:

• For any prime $$p \mid m$$, we have $$p \mid km$$. Since $$p \nmid n$$, we have $$p \nmid b$$ and hence, $$p \nmid (km+b)$$.
• For any prime $$p \mid a$$, we have $$p \mid k$$, and hence $$p \mid km$$. Since $$p \nmid b$$, we have $$p \nmid (km+b)$$.
• For any prime $$p \mid b$$, we have $$p \mid n$$, and hence $$p \nmid m$$. Moreover, as $$p \mid b$$, we have $$p \nmid k$$. Thus, $$p \nmid (km+b)$$.

In conclusion, we can see that none of the primes dividing $$m$$ or $$n$$ divide $$km+b$$, which is clearly between $$km+1$$ and $$(k+1)m$$ since $$km < km+b \leqslant km+n \leqslant km+m$$. This solves the problem, since for any choice of $$c$$, the interval $$(c,c+2m]$$ contains positive integers $$km+1,km+2,\ldots,(k+1)m$$ for some positive integer $$k$$.

• Amazing! This solution is straightforward to turn into an algorithm $f(n, m, c) = d$ that calculates an explicit example $d$ for any given input. Very nice!
– kate
Sep 8, 2020 at 3:53