8
$\begingroup$

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?

$\endgroup$
6
  • 8
    $\begingroup$ If prime $p$ divides $2^p+11$, then by Fermat's little theorem $p$ divides $2+11=13$ $\endgroup$ Sep 10, 2020 at 2:07
  • $\begingroup$ That only covers primes? $\endgroup$
    – markvs
    Sep 10, 2020 at 2:24
  • $\begingroup$ How do I find solution? By asking in math stack exchange. $\endgroup$ Sep 10, 2020 at 2:48
  • $\begingroup$ 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. $\endgroup$ Sep 10, 2020 at 4:26
  • 3
    $\begingroup$ In OEIS no sequence for c=-11 $\endgroup$ Sep 10, 2020 at 7:17

3 Answers 3

5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
4
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .