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?

[Nag52] Jitsuro Nagura. On the interval containing at least one prime number. Proceedings of the Japan Academy, 28(4):177–181, 1952.

  • $\begingroup$ Ok. Finally read the whole question. Deleted my answer. $\endgroup$ – Aryabhata Mar 5 '11 at 2:50
  • $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Mar 5 '11 at 2:56
  • $\begingroup$ Ahh, I see! No worries, glad to have helped :-) $\endgroup$ – Aryabhata Mar 5 '11 at 3:00
  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ 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? $\endgroup$ – Tsuyoshi Ito Mar 5 '11 at 17:09
  • $\begingroup$ @Tsuyoshi: I added an edit answering this question. $\endgroup$ – Eric Naslund Mar 5 '11 at 17:31
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Mar 6 '11 at 15:03
  • $\begingroup$ Awesome, answer. THough i understand a little, i wish I could learn ANT from you. $\endgroup$ – user9413 May 21 '11 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.