Do $n=2m+1$ and $\big(2^m\bmod(m\cdot n)\big)\in\{n+1,3n-1\}$ imply $n$ prime?

Solution 1:

After Peter Košinár's answer/comment, it is settled that the answer to the title's question is no. And that even the stronger requirements: $n=2m+1$, $2^m\equiv\pm1\pmod n$, and $2^{(m-1)/2}\equiv\pm1\pmod m\ $ do not imply $n$ prime. Many of the $m=(4^p-1)/3$ with $p$ prime turn out to be counterexamples, including $p$ among

23, 29, 41, 53, 89, 113, 131, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953, 1013, 1019, 1031, 1049, 1103, 1223, 1229, 1289, 1409, 1439, 1451, 1481, 1499, 1511, 1559, 1583, 1601, 1733, 1811, 1889, 1901, 1931, 1973, 2003, 

It holds that if $n=2m+1$ with $m$ prime and $2^m\equiv\pm1\pmod n$, then $n$ is prime. That's proven by Fedor Petrov here, with details there.

Question remaining open: do $n=2m+1$, $n$ and $m$ passing the strong pseudoprime test to base 2 imply $n$ prime?