Prove that $n=\frac{4^p+1}{5}$ is a strong 2-pseudoprime for all $p>5$ I want to prove that  $n=\frac{4^p+1}{5}$ is a strong 2-pseudoprime for all $p>5$ where $p$ is a prime.
i.e. $n$ is a composite number which passes the Miller-Rabin test. 
It is easy to check that it is indeed a composite no.
We write $n-1=2^st$ where $t$ is an odd number. $n$ passes the test if either
$$a^t\equiv1 \space(mod \space n)$$ or
$$a^{{2^i}t}\equiv-1 \space(mod \space n)$$ for some $i<s$.
Then $n-1=\frac{4^p+1}{5}-1= \space ... \space=2^2(\frac{4^{p-1}\space-1}{5})$so $s=2$ and $t=\frac{4^{p-1}\space-1}{5}$
So is $$2^{\frac{4^{p-1}\space-1}{5}}\equiv1\space(mod \space \frac{4^p+1}{5})$$
or
$$2^{2^1(\frac{4^{p-1}\space-1}{5})}\equiv-1\space(mod \space \frac{4^p+1}{5})$$?
I checked the results for the first few primes (Yup, WolframAlpha did help).
It turns out that it is always the latter case which holds
My guess is that:
if $p\equiv3 \space (mod \space 4)$ then $2^{\frac{4^{p-1}\space-1}{5}}\equiv2^p\space(mod \space \frac{4^p+1}{5})$
if $p\equiv1 \space (mod \space 4)$ then $2^{\frac{4^{p-1}\space-1}{5}}\equiv-2^p\space(mod \space \frac{4^p+1}{5})$.
Squaring both sides and the result follows. Could anyone show why my guess is correct (or not?)?
 A: I think you are expected to make the following observations:


*

*By Little Fermat $(4^{p-1}-1)$ is divisible by $p$. Hence so is $(4^{p-1}-1)/5$.

*Clearly $(4^{p-1}-1)/5$ is an odd integer, so the number $e_p:=2(4^{p-1}-1)/5$ is an odd multiple of  $2p$, say $e_p=2pT$ with $T$ odd.

*It is clear that $2^{2p}\equiv-1\pmod n$, so by item #2 we also have
$$2^{e_p}=2^{2pT}\equiv(-1)^T=-1\pmod n.$$


So after step 3 we have confirmed your first finding. Which also shows that $2$ is an "anti-witness".
A: Just want to fill in the gap that $n$ is indeed a composite number
since $p$ is an odd prime, $(p+1)/2$ is a positive integer.
$4^p+1=(2^p+1)^2-2^{p+1}=(2^p+1)^2-2^{2((p+1)/2)}=(2^p+2^{(p+1)/2}+1)(2^p-2^{(p+1)/2}+1)$
We show that $5$ divides one of $(2^p+2^{(p+1)/2}+1)$ and $(2^p-2^{(p+1)/2}+1)$. What's left from the dividend is $>1$ and so multiplied by that not divisible by $5$ we get a composite no.
There are 4 cases:
-when $p=4k+1$ and $k$ is odd
-when $p=4k+1$ and $k$ is even
-when $p=4k+3$ and $k$ is odd
-when $p=4k+3$ and $k$ is even...
for example, when $p=4k+3$ and $k$ is odd
$2^p+2^{(p+1)/2}+1=2^{4k+3}+2^{2k+2}+1=8(16^k)+4(4^k)+1\equiv3(1^k)-(-1)^k+1\equiv0\space(mod\space5)$
