I thought I could prove it in the case of a negative sign but I can only show that in this case, for fixed $n$, there can be only finitely many counterexamples. Nothing magical about $3$ by the way.

Let $p$ be prime and $n$ an integer such that $N=2^np + 1$ is such that, for some integer $a$ we have $a^{(N-1)/2} \equiv -1 \pmod N$. Then $N$ is prime or $p \le a^{2^{n-1}}/2^n$.

Proof: Let $m$ be the order of $a$ modulo $N$, then $m | 2^np$, so $m = 2^k$ or $2^kp$ for some $k \le n$. Since we have $-1$ in the congruence in the hypothesis, we conclude that $k=n$. If $m = 2^np$, then $N$ is prime ($\phi(N)=N-1$ iff $N$ is prime). The only other possibility is $m=2^n$. Assume that's the case. Then $2^n | \phi(N)$ but we cannot have $p|\phi(N)$ as that would force $\phi(N) \ge N-1$. So $(p,\phi(N))=1$ and the congruence $a^{(N-1)/2} \equiv -1 \pmod N$, then implies that $a^{2^{n-1}} \equiv -1 \pmod N$. So $N \le a^{2^{n-1}} + 1$ giving the result.