characterisation of $n$ as prime using min values of $x$ such that $nx+1$ or $nx$ is square

Question

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

Answer 1

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

Answer 2

The 'only if' part is true - I'm still wondering about the only 'if' part. I put a proof of the 'only if' part here and maybe edit my thoughts on the 'if' part in later if I find something interesting.

In fact if $n$ is prime then $k$ is at least $n - 2$ and $l$ is at least $n$.

Proof of $k \geq n - 2$. We have that $kn + 1 = m^2$ for some $m$ so $m^2 - 1 = kn$ so $kn = (m + 1)(m-1)$.

Since $n$ is prime it follows from Euclid's lemma that $n$ divides either $m + 1$ or $m - 1$. Suppose $n|(m - 1)$ so that $m - 1 = na$ then $kn = na(na + 2)$ so $k = a(na + 2) \geq (na + 2) \geq n + 2$. Suppose $n|(m + 1)$ so that $m + 1 = nb$ then $kn = nb(nb -2)$ so that $k = b(nb - 2) \geq n - 2$.

Proof of $l \geq n$: again by Euclids lemma $ln = m^2$ implies $n|m$ and hence $n^2|m^2$ so $ln = an^2$ hence $l = an \geq n$.