8
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Sep 1, 2020 at 4:00
  • $\begingroup$ 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. $\endgroup$ Sep 1, 2020 at 5:06
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 1, 2020 at 6:18
  • 1
    $\begingroup$ Thanks for the update, it really is very nice. $\endgroup$ Sep 9, 2020 at 6:57

1 Answer 1

7
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – kate
    Sep 8, 2020 at 3:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .