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

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