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

  • $\begingroup$ How did you prove that $n$ is a composite? $\endgroup$ – Jyrki Lahtonen May 15 '17 at 13:39
  • $\begingroup$ Just finish typing the proof that $n$ is a composite. I thought it was easier than the core of the question though D: $\endgroup$ – user441558 May 15 '17 at 14:03

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".

  • $\begingroup$ Thinking about your second guess $\endgroup$ – Jyrki Lahtonen May 15 '17 at 13:23
  • $\begingroup$ Hmm... it seems my guess is just useless... that's fine. but still expecting it to be verified D: . I have no idea. $\endgroup$ – user441558 May 15 '17 at 13:37

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

  • $\begingroup$ Thank you! Silly to forget about this :-) $\endgroup$ – Jyrki Lahtonen May 15 '17 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy