Can I find all solutions of $2^{n-1}\equiv k\mod n$?

Question

Suppose$\ k\ge 2\ $ is a positive integer.

Can I find all positive integers $\ n>1\ $ with $$2^{n-1}\equiv k\mod n$$ ?

I only found out yet that there is always a solution if $\ k>2\ $ and $\ k-1\ $ is not a power of $\ 2\ $. In this case, $\ k\ $ has an odd prime factor $\ q\ $, for which we have $\ 2^{q-1}\equiv k\mod q\ $ as desired.

I am particularly interested whether for $\ k=5\ $, there is a solution and whether for $\ k=11\ $, there is a solution besides $\ n=5\ $. Finally, for $\ k=3\ $, is $\ 10669\ $ the only solution?

Answer 1

Check out sequences in the OEIS linked from 2^n mod n OEIS Wiki page. In particular, you'll find that

• For $k=5$, there are many known solutions given by the odd terms of A128123.
• For $k=3$, solutions are given by the odd terms of A128122, and 10669 is the only one below $10^{16}$.

ADDED. Overall, I believe there are infinitely many solutions for most integer $k$ (except some rare cases like $k=-1$). However, I doubt there exists a simple formula for getting them all. What we can hope for is getting all solutions below a certain bound.

From practical perspective, there is a number of tricks that may speed up the search for solutions, e.g. see Joe Crump's 2^n mod n = c webpage.

Answer 2

Clearly n can not be prime. I had following experiment:

$2^{4-1}=8=2\times 4 +0$

$2^{6-1}=32=5\times 6 +2$

$2^{8-1}=128=16\times 8+0$

$2^{9-1}=256=28\times 9 +4$

$2^{10-1}=512=51\times 10+2$

$2^{12-1}=2042=170\times 12 +8$

$2^{14-1}=8192=585\times 14 +2$

$2^{15-1}=16384=1092\times 15 +4$

$2^{16-1}=32768=2048\times 16 +0$

$2^{17-1}=65536=3855\times 17 +1$

$2^{18-1}=131072=7281\times 18+14$

$2^{33-1} ≡4 \mod 33$

$2^{27-1} ≡13 \mod 27$

A: if $n=2^t$ then $k=0$

B: if $n-1=2^t$ and $t=2s$ then $k=1$

C: if $n-1=2^t$ and $t=2s+1$ then $k=2^u$

D: Else $k=2^v$ or $k=k_1$; $k_1∈N$