Prove $n\geq 3$ is prime or the largest non-trivial factor of $n$ is at least $3\sqrt{n}$

Question

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 know this question is related to Fermat factorisation but I can't see how to approach it.

Answer 1

Let's look at the contrapositive.

If $n\geq 3$ is odd, not prime and the largest non-trivial factor of $n$ is less than $3\sqrt{n}$, then $a^2-n$ is a perfect square for some $a$ in the interval $\tfrac23\sqrt{n}<a<2\sqrt{n}$.

So, let's see. We start by writing $n=xy$, where $x,y$ are integers less than $3\sqrt{n}$. Now we'll try to find an $a$ in the right interval such that $a^2-n$ is a square, or,

$$a^2-xy=m^2$$

That equation can be rewritten as $(a-m)(a+m)=xy$. Now if $x+y$ is even, then we may pick $a=\frac{x+y}2$ and $m=|\frac{x-y}2|$. Now we merely need to prove that we can pick $x$ and $y$ such that $x+y$ is even. This is quite obvious; if $n$ is odd, $x$ and $y$ then have to be both odd, so that $x+y$ is even. So, we've proven the contrapositive and from that follows the theorem must be true.