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?
[Nag52] Jitsuro Nagura.  On the interval containing at least one prime number.  Proceedings of the Japan Academy, 28(4):177–181, 1952.
 A: 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$.
