Given $a^2 − n$ is not a perfect square for any integer $a$ in the interval $\tfrac23\sqrt{n} < a < 2\sqrt{n}$, prove $n \geq 3$ ($n$ odd) is prime or the largest non-trivial factor of $n$ is at least $3\sqrt{n}$.
I believe you are meant to use Fermat factorisation, but I dont see how to relate it to the question.
Let $n$ be odd and $\ge 3$. Assume $n=uv$ with $\sqrt n\le u<3\sqrt n$. Note that $u,v$ are both odd. Then with $a:=\frac{u+v}2$, $b:=\frac{u-v}2$, we have $n=uv=(a+b)(a-b)=a^2-b^2$.
If $\sqrt n\le u<2\sqrt n$, we get $\frac12\sqrt n<v\le \sqrt n$ and hence $$ \frac23\sqrt n<\frac{\sqrt n+\frac12\sqrt n}2<a<\frac{2\sqrt n+\sqrt n}2<2\sqrt n.$$ If $2\sqrt n\le u<3\sqrt n$, we get $\frac13\sqrt n <v\le\frac 12\sqrt n$ and so again $$ \frac23\sqrt n<\frac{2\sqrt n+\frac13\sqrt n}2<a<\frac{3\sqrt n+\frac12\sqrt n}2<2\sqrt n.$$
Remark: Already accorindg to the findings above, the interval $\frac23\sqrt n<a<2\sqrt n$ can be shortened to $$\frac34\sqrt n<a< \frac74\sqrt n.$$ But we might also note that $u+v=u+\frac nu$ is strictly increasing for $u\ge \sqrt n$, hence $\sqrt n\le u < 3\sqrt n$ actually leads to $2\sqrt n\le u+v<3\frac13\,\sqrt n$, i.e., we can shorten the interval even further to half the original length: $$ \sqrt n\le a<\frac 53\sqrt n.$$