On existence of an integer between $\sqrt{n}$ and $\sqrt{2n}$ coprime to $n$

I have one proof of the following statement, and I would like to know if there is a simpler proof. I am not sure if “simpler” is the right word or not but, for the purpose of this question, I prefer an elementary proof rather than a short proof depending on a powerful and difficult-to-prove theorem.

For any integer $n \ge 171$, there exists an integer $m$ coprime to $n$ satisfying $n\lt m^2 \lt 2n$.

The proof which I have actually gives an additional guarantee that $m$ is a prime. I do not need this guarantee and want a simpler proof if there is one.

My proof uses the method used by Nagura [Nag52], which I suspect may be overkill for this purpose. By the same argument as the one in [Nag52], we can prove that for every $x \geq 16769$, there exists a prime between $x$ and $2^\frac 14 x$, and we can verify that the same conclusion holds for $x \ge 32$ by calculation. This implies that for $n \ge 32^2=1024$, there exist at least two primes between $\sqrt{n}$ and $\sqrt{2n}$. Because both primes are greater than $\sqrt{n}$, at least one of them must be coprime to $n$. The case of $171 \le n \le 1023$ can be verified by calculation.

Is there a simpler proof of the statement above?

• Ok. Finally read the whole question. Deleted my answer. – Aryabhata Mar 5 '11 at 2:50
• @Moron: Sorry, the revision 1 of the question was unclear in what I meant by “simpler.” I read your answer before you deleted it, and it was helpful. Thanks a lot. – Tsuyoshi Ito Mar 5 '11 at 2:56
• Ahh, I see! No worries, glad to have helped :-) – Aryabhata Mar 5 '11 at 3:00
• Do you really have a relatively elementary proof that there is a prime between $\sqrt{n}$ and $\sqrt{2n}$? If so, that would probably publishable. – Thomas Andrews Jul 6 '16 at 12:43

I will show what you want for sufficiently large $n$.

First question: How many squares are between $n$ and $2n$. Well we have $$\#\text{of squares}=\lceil\sqrt{2n}-1\rceil-\lceil\sqrt{n}-1\rceil\geq\sqrt{2n}-\sqrt{n}-2=(\sqrt{2}-1)\sqrt{n}-2\geq \frac{\sqrt{n}}{3}$$ for sufficiently large $n$. So lets look at the square roots of these squares, which form a sequence of more than $\sqrt{n}/3$ consecutive integers. (This is fine since $\gcd(n,m)=1$ if and only if $\gcd(n^2,m)=1$) The goal is then to show that one of these integers in this sequence is relatively prime to $n$.

Recall the elementary Eratosthenes-Legendre sieve which says that:

Theorem: For any real $x$ and any $y\geq 0$, we have $$S(x,y;n)=\frac{\phi(n)}{n}y+O\left(2^{\omega(n)}\right)$$ where $S(x,y;n)$ is the number of integers $m$ in the interval $x<m\leq x+y$ for which $(n,m)=1$.

Using this theorem, combined with the fact that $2^{\omega(n)}\ll_{\epsilon} n^\epsilon$, and the fact that $$\frac{\phi(n)}{n}\geq \frac{C}{\log\log n},\ \ (C>0)$$ the result then follows for sufficiently large $n$.

Notice that this proof generalizes to show that for any $k$, there exists $N$ such that for any $n>N$ there exists $m\in \left(\sqrt[k]{n},\ \sqrt[k]{2n}\right)$ for which $\gcd(m,n)=1$. In other words, we can show:

For any $k$, taking $n$ large enough guarantees that there will be a $k^{th}$ power between $n$ and $2n$ that is also relatively prime to $n$.

Hope that helps,

Remark: The key fact which makes this proof work is that $2^{\omega(n)}\ll_\epsilon n^\epsilon$ for every $\epsilon$. The Eratosthenes-Legendre Sieve is really what you get when you try the simplest approach to evaluating $S(x,y;n)$. It follows directly from the inclusion-exclusion principle.

Added Proof: Why is it true that $$\frac{\phi(n)}{n}\geq \frac{e^{-\gamma}}{\log\log n}+O\left(\frac{1}{(\log\log n)^2}\right)?$$ This follows from Mertens formulas along with Chebyshevs estimates. The error term can be removed by making the constant smaller, which is what I wrote down above, but lets prove this form. Look at the $n$ which minimize $\phi(n)/n$ for their size. These will be of the form $$\prod_{p\leq y}p,$$ that is the product of the first few primes. (*Prove these numbers do indeed minimize) Taking logarithms introduces $\theta(y)$, so we can deduce $\log \log n = \log y +O(1)$ by Chebyshevs estimate. Next $$\frac{n}{\phi(n)}=\prod_{p\leq y}=\left( 1-\frac{1}{p}\right)^{-1}=e^\gamma\log y+O(1)$$ is one of Mertens formulas. Taking reciprocals yields $$\frac{\phi(n)}{n} = \frac{e^{-\gamma}}{\log \log n} + O\left(\frac{1}{(\log \log n)^2}\right)$$ as desired.
That result is actually stronger than we need. All the above proof required was that $n^{-\epsilon}\ll_\epsilon\phi(n)/n$ for every $\epsilon$.

• This seems to be the right approach. Thanks a lot. I have one question: how do we prove that φ(n) / n ≥ C / log log n? – Tsuyoshi Ito Mar 5 '11 at 17:09
• @Tsuyoshi: I added an edit answering this question. – Eric Naslund Mar 5 '11 at 17:31
• Thanks! I had never heard of the Mertens formula (MathWorld). I will consult some textbook on number theory. I will wait for a day or two and accept your answer unless the situation changes. – Tsuyoshi Ito Mar 6 '11 at 15:03
• Awesome, answer. THough i understand a little, i wish I could learn ANT from you. – user9413 May 21 '11 at 17:36