If $\min\{x \in\mathbb{N} : xn+1 \text{ is a square}\} \geq \frac{n}{4}$ then n is prime. 
Let $n$ be a odd natural number greater than 3 and $k=\min\{x \in\mathbb{N} : xn+1 \text{ is a square}\}$ and $t=\min\{x \in\mathbb{N} : xn \text{ is a square}\}.$ If $k>\frac{n}{4}$ and $t>\frac{n}{4}$ then n is prime.

I proved second direction easily, so I don't cite it. If $n$ is composite and isn't squarefree the hypothese about $t$ is false and it's very easy from prime decomposition. I have problems wiith a part about composite squarefree $n$. I tried prime decomposition, I tried find explicitly k to contradict. I spent a few hours. I would be very grateful for any hint.

If $n\in \mathbb{N}$ is odd and not a prime power, then there is always an $a$ such that $1 < a \leqslant \frac{n-1}{2}$ and $a^2 \equiv 1 \pmod{n}$. Then it follows that
$$k \leqslant \frac{a^2-1}{n} < \frac{n^2/4}{n} = \frac{n}{4}\,.$$
To see that such an $a$ exists, let $p$ be a prime dividing $n$, and write $n = p^r\cdot m$ with $p \nmid m$. Since $n$ is not a prime power, we have $m > 1$. By the Chinese remainder theorem, there is a $0 < b < n$ such that $b \equiv 1 \pmod{p^r}$ and $b \equiv -1 \pmod{m}$. Since $b \equiv 1 \pmod{p^r}$ we have $b \neq n-1$, and since $b \equiv -1 \pmod{m}$ we have $b \neq 1$, thus $1 < b < n-1$. If $b \leqslant \frac{n-1}{2}$, put $a = b$, else put $a = n-b$. Then $1 < a \leqslant \frac{n-1}{2}$, and $a^2 \equiv (\pm 1)^2 \equiv 1 \pmod{p^r}$ and $a^2 \equiv (\mp 1)^2 \equiv 1 \pmod{m}$, so we indeed have $a^2 \equiv 1 \pmod{n}$.
If $n$ is an odd prime power and not a prime, then $n = p^r$ for some odd prime $p$ and $r > 1$. If $r$ is even, then $n$ is already a square and so $t = 1 < \frac{n}{4}$. If $r$ is odd, then $pn$ is the smallest square multiple of $n$, and $t = p \leqslant \frac{n}{p^2} \leqslant \frac{n}{9} < \frac{n}{4}$.
