How do I find solutions to $2^n+11 \equiv 0 \pmod n$?

Solution 1:

How can I find other solutions that satisfies the equation

Joe Crump and others have extensively studied the $2^n \equiv c \pmod n$ problem. You can read about findings and methods here. They typically require brute force computer searches, applying some elementary number theory to limit the search range.

To paint some broad strokes: determine for each prime $p$ whether it is possible for $p$ to divide $n$. If $2^{kp} + 11 \equiv 0 \pmod{n}$, then we demand $2^k + 11 \equiv 0 \pmod{p}$, which is either impossible or which translates to a requirement that $k \equiv a \pmod{b}$ for some $a$ and $b$ which divides $\phi(p) = p-1$, with those $a$ and $b$ easily computed by brute force. This creates candidate forms of $n$, such as $n=29k$ where $k\equiv 11 \pmod{28}$.

This correspondence shows how some have taken these approaches, together with optimistic guesses that $n$ might have few prime factors, to generate solutions for other values of $c$. This general approach seems likely to similarly generate solutions for $c=-11$.

Solution 2:

After extending the search for a solution in the range $10000000000 \leq n \leq 20000000000$, a solution was finally found at $n=16043199041$ by one of my friends. Also, a sequence in OEIS has been established for the equality.

Solution 3:

$n=383979411456776027$

Let valid prime $p$ such that exist $k$ for $2^k\equiv -11\pmod{p}$. For brute force need pick up set triples $(p,k,h)$, where $h=ord_p(2)$. Then $n=p(k+j\cdot h)$, where $j$ is brute force step. For speed up calculation can use CRT of two valid triples.

gp-code:

 P= read("n11.dbt");
 for(i=2, #P~, for(j=1, i-1,
  c= iferr(chinese(Mod(P[i,1]*P[i,2], P[i,1]*P[i,3]), Mod(P[j,1]*P[j,2], P[j,1]*P[j,3])), Err, 0);
  if(c,
   k= lift(c); h= c.mod;
   d= 10^10\h; 
   for(t=d, d+10^4,
    n= k+t*h; \\print(h"    "n);
    if(Mod(2,n)^n==-11,
     print(n"    "k"    "h"    "t)
    )
   )
  )
 ))

File "n11.dbt" contains valid triples: [13, 1, 12; 23, 10, 11; 29, 11, 28; 43, 5, 14; 47, 17, 23; 71, 11, 35; 83, 65, 82; 89, 8, 11; 97, 35, 48; 101, 63, 100; ...]. For $p<10^7$ i pickuped 180561 triples, but still they have many non-valid triples, becose for me algorithm selecting triples is not simple.