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

In recent days, I have been studying the equation $$m^n+h \equiv 0 \pmod n$$ where $$m,n \in \mathbb N$$ and $$h\in\mathbb Z$$, and I have noticed that $$2^n+11 \equiv 0 \pmod n$$ have no solutions in $$1 \leq n \leq 2000000000$$ except for $$1$$ and $$13$$. How can I find other solutions that satisfies the equation, or prove otherwise that no solutions $$>13$$ exists?

• If prime $p$ divides $2^p+11$, then by Fermat's little theorem $p$ divides $2+11=13$ Sep 10, 2020 at 2:07
• That only covers primes? Sep 10, 2020 at 2:24
• How do I find solution? By asking in math stack exchange. Sep 10, 2020 at 2:48
• The proof for the falsity of the condition for primes (except 13) and pseudoprimes base 2 is quite simple, yet I can't come up with a proof for the remaining numbers. Sep 10, 2020 at 4:26
• In OEIS no sequence for c=-11 Sep 10, 2020 at 7:17

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$$.

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.

$$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.