characterisation of $n$ as prime using min values of $x$ such that $nx+1$ or $nx$ is square Let $n\ge 5$ be an odd integer and
$k\ =\ \min\{x\in\mathbb{N}\colon nx+1\text{ is a perfect square}\}$
$l\ =\ \min\{x\in\mathbb{N}\colon nx\text{ is a perfect square}\}$
Prove that $n$ is a prime iff $\min(k,l)>\frac{n}{4}$.

$n$ is prime $\implies$ $k,l>n/4$:
We have $l=n>n/4$. From $kn=(a-1)(a+1)$ it follows that $n\mid a-1$ or $n\mid a+1$, so $a+1\geq n$. Using this, $k=(a^2-1)/n\geq n-2>n/4$ because $n>2$. (In fact, as noted in the comments below, $k=n-2$ because $n(n-2)=(n-1)^2-1$.)
$k,l>n/4$ $\implies$ $n$ is prime:
If $n=m^2l$ with $l$ square-free, then clearly $l= \min\{x\in\mathbb{N}\colon nx\text{ is a perfect square}\}$. From $l>n/4$ it follows that $m^2<4$, so $m=1$, i.e.: $n=l$ is square-free. Let $n=p_1\cdots p_t$ be its prime factorisation.
Suppose $t>1$, i.e., $n$ is not prime.
By the Chinese Remainder theorem, the congruence $a^2\equiv1\pmod n$ has $2^t$ solutions (which rise by composing the solutions for the congruences $a^2\equiv1\pmod{p_j}$). If $a$ is a solution, then so is $-a$. $2^{t-1}\geq2$ solutions are in the interval $[0,n/2]$ (one of which is $1$). Take such a non-$1$ solution, and say $xn=a^2-1$. Then $x<(n/2)^2/n=n/4$, contradicting $k>n/4$. $\square$
The essential argument was the following: if $a^2\equiv1\pmod n$ has at least $3$ solutions, then it has a solution with $1<a\leq n/2$. And for it to have at least $3$ solutions, it suffices that $n$ has at least two odd prime divisors. More specifically:
Fact: If $n=2^sm$ ($m$ odd) has $t$ distinct odd prime divisors, then the number of solutions to $x^2\equiv1\pmod n$ is $2^{t+2}$ if $s\geq3$, $2^t$ for $s=0,1$ and $2^{t+1}$ for $s=2$.
