$n$ is an odd number, with a prime factorization containing only primes $\equiv 1 \mod 4$. $b$ is a root of $-1$ ($b^2 \equiv -1 \mod n$), $1<b<n$.
I have been unsuccessfully looking for a proof that when $b$ is a multiple of 4, then $b < \frac{n}{2}$.
Example: $n=17$, $b=4$. The other root of $-1$, namely $17-4=13$, is odd and lies in the second half of the interval $[1,n]$.
Other examples: $n=29, b=12$; $n=3277,b=1032$.
Who can help me with this proof?
We can easily play the odds by starting with an $n$ which has a lot of modular square roots: if $n$ has $k$ distinct prime factors (of the desired form) then it will have $2^k$ square roots of $-1$. Since these will, in all likelihood, be distributed randomly in $(1,n)$, then gathering $8$ candidates will give us a very good chance ($1 - 2^{-8} \approx 99.6\%$) of finding one in the second half. In order to get $8$ multiples of $4$ we should aim for $32$ roots altogether. So let's pick $k=5$:
$$n = 5 \cdot 13 \cdot 17 \cdot 29 \cdot 37 = 1185665,$$
And we easily verify (Wolfram Alpha) that $1076028$ is a square root of $-1$ that is a multiple of $4$ that is very far into the second half.
I'm sure that smaller examples exist, but this was almost guaranteed to flush out an example on the first try.
EDIT: Smallest example is $8^2 \equiv -1 \pmod{13}$. You must have been pretty unlucky to find enough false positives to believe this was true!