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