Prove that $n=\frac{4^p+1}{5}$ is a strong $2$-pseudoprime for all $p>5$

Question

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 \pmod{n}$$ or $$a^{{2^i}t}\equiv-1 \pmod{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\pmod{\frac{4^p+1}{5}}$$ or $$2^{2^1(\frac{4^{p-1}\space-1}{5})} \equiv -1 \pmod{\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 \pmod{4}$ then $2^{\frac{4^{p-1}\space-1}{5}}\equiv2^p \pmod{\frac{4^p+1}{5}}$

if $p\equiv1 \space \pmod{4}$ then $2^{\frac{4^{p-1}\space-1}{5}}\equiv-2^p\space \pmod{\frac{4^p+1}{5}}$.

Squaring both sides and the result follows. Could anyone show why my guess is correct (or not?)?

Answer 1

I think you are expected to make the following observations:

1. By Little Fermat $(4^{p-1}-1)$ is divisible by $p$. Hence so is $(4^{p-1}-1)/5$.
2. 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.
3. 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".

Answer 2

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)$