Proof the following statement or give a counterexample:
Let $n$ be a natural number.
If $n \equiv 1 \mod 4$ and $4^\frac{n-1}{4} \equiv -1 \mod n$, then $n$ passes the Miller-Rabin test to the basis 2
I strongly believe that the statement is true but could not find a proof for it.
The Miller-Rabin test works as follows:
Let $n$ be an odd number (true in our case) and $a$ the basis ($2$ in this question). Calculate $d$ (odd) and $j$ such that
$$n-1=d \cdot 2^j$$.
We then check if either
$$a^d \equiv 1 \pmod n$$
or (for some $r$ with $0 \leq r \leq j$)
$$a^{d \cdot 2^r} \equiv -1 \pmod n.$$
which must always be the case if $n$ is prime.
Since $4^\frac{n-1}{4} = 2^\frac{n-1}{2}$, and $\frac{n-1}{2} = d*2^{j-1}$, Miller-Rabin is passed with $r = j-1$.