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

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

Equivalently, for $n=2m+1$, do $2^m\equiv\pm1\pmod n$ and $2^m\equiv2\pmod m$ imply $n$ prime?
Note: equivalence follows from the Chinese Remainder Theorem for $m>2$, and examination otherwise. $2^m\equiv\pm1\pmod n$ is an Euler test for $n$.

What if we add the stronger requirements that $2^{(m-1)/2}\equiv\pm1\pmod m$ ? That $m$ pass the strong pseudoprime test to base 2?

The $n$ with $m$ prime that pass the test include all the safe primes (OEIS A005385) above $5$. The corresponding $m$ are Sophie Germain primes (OEIS A005384).
Proof: safe primes $p=2q+1$ match $2^q\equiv\pm1\pmod p$ by Euler's criterion, and match $2^q\equiv2\pmod q$ by Fermat's little theorem.

I fail to prove that conversely, the $n=2m+1$ with $m$ prime that pass the test include nothing but the safe primes.

There are a few other $n$ that pass the test, dubbed pseudo-safe-primes, A300193; terms less than $2^{42}$ b300193; first ones:

683, 1123, 1291, 4931, 16963, 25603, 70667, 110491, 121403, 145771, 166667, 301703, 424843, 529547, 579883, 696323, 715523, 854467, 904103, 1112339, 1175723, 1234187, 1306667, 1444523, 2146043, 2651687, 2796203, 2882183, 3069083, 3216931, 4284283, 4325443, 4577323, 5493179, 5764531, 9949943,

The smallest even $m$ are for $n=252\,435\,584\,573$, $1\,200\,060\,997\,853$, $2\,497\,199\,739\,653$, $453\,074\,558\,824\,253$... which are prime. Any such even $m$ is an even pseudoprime (OEIS A006935).

All odd $m$ are pseudoprimes (OEIS A001567) passing a Fermat test, with the corresponding $n$ passing a strong pseudoprime test.

• You might not like the number $m=23456248059221$ :-) – Peter Košinár Mar 6 '18 at 1:19
• @Peter Košinár: that's an answer to two of out of the three questions! $n=2m+1=(2^{47}+1)/3=283*P_{12}$. Further, $m=(2^{46}-1)/3$ pass the Euler test. All that's left pending is: does there exist composite $n=2m+1$ with $n$ and $m$ passing the strong pseudoprime test? – fgrieu Mar 6 '18 at 12:04
• As you have correctly observed, I used the standard construction $m=(4^p-1)/3$ for Fermat pseudoprimes and just tested $n=(2m+1)$ for non-primality. While it guarantees $m$ to satisfy Euler criterion too, it fails the extended Euler-Jacobi version of it where $\pm 1$ is replaced by Jacobi symbol (and thus also fails the strong pseudoprimality test). When I tried to do something similar with one specific explicit construction of strong pseudoprimes, it failed miserably: the resulting $n$ failed even the Fermat test. I will keep playing with a few more ideas, though. – Peter Košinár Mar 6 '18 at 13:02

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