Is $N=3\cdot 2^k+1$ prime if and only if $2^{N-1}\equiv 1 \pmod N$?

162 Views Asked by At

Is the following statement true?

Let $k\geq 1$ be an integer and $N=3\cdot 2^k+1$. Then $N$ is a prime prime if and only if $2^{N-1}\equiv 1 \pmod {N}$

One implication is simply a Fermat's Little Theorem, so the difficult part is proving or disproving that $2^{N-1}\equiv 1 \pmod {N}$ implies $N$ is a prime. Or in other words showing whether there is a $k$ such that $N$ is a Fermat pseudoprime to base $2$ (Poulet Number).

I have checked the claim holds for $k\leq 15000$.

As for the proof, we know complete factorization of $N-1$ so I was thinking of Lucas primality test, for which it would be sufficient to show that if $2^{N-1}\equiv 1 \pmod {N}$, then $2^{\frac{N-1}{3}}\not\equiv 1 \pmod {N}$ and $2^{\frac{N-1}{2}}\not\equiv 1 \pmod {N}$. Then I thought about Poclikngton primality test, but it requires a prime $p\mid N-1$ with $p>\sqrt{N}-1$ which we don't have (as $p=2,3$). As noted by Peter in comments, the last requirement can be removed in which case it's sufficient to prove $\gcd(2^{\frac{N-1}{3}}-1,N)=\gcd(2^{\frac{N-1}{2}}-1,N)=1$, however that seems stronger than what suffices for Lucas' test.

I don't expect this result to be anything new or profound, I just have not found/proven it yet... Then again, I am not way too familiar with primality tests.

As from where this comes from, I just did a computer search to look for similar criterion as Lucas-Lehmer test but for numbers of form $3\cdot 2^k+1$ and it found a match which when solving the recurrence to a closed form gave the statement above.