c=2^{n} mod n |
Solutions 'n' in order
(gauranteed to be in sequence) |

3 |
4700063497, 3468371109448915, 8365386194032363, 10991007971508067 |

5 |
19147, 129505699483, 674344345281 |

7 |
25, 1727, 3830879, 33554425, 19584403931,
25086500333 |

9 |
2228071, 16888457, 352978207, 1737848873,
77362855777, 567442642711 |

11 |
262279, 143823239, 382114303, 1223853491,
381541784791, 556985326431 |

13 |
95, 4834519, 156203641, 135466795859 |

15 |
481, 44669, 1237231339, 1546675117, 62823773963,
284876771881, 1119485807557 |

17 |
45, 99, 53559, 1143357, 2027985, 36806085,
1773607905, 3314574181, 1045463125509, 1226640523999 |

19 |
2873, 10081, 3345113, 420048673, 449349533,
2961432773, 19723772249, 821451792317, 1207046362769 |

21 |
3175999, 54895651 |

23 |
555, 80481, 41546509, 967319517, 2196415073,
5094927987 |

25 |
95921, 24960497, 3594750257 |

27 |
174934013, 20958230885 |

29 |
777, 56679, 274197, 2359749, 2804637, 4657821,
5212515021, 49330976277, 831447303027 |

31 |
140039, 404167811, 1767944407 |

2^{n} mod n = 3, n =
8365386194032363

2^{n} mod n = 3, n =
63130707451134435989380140059866138830623361447484274774099906755

2^{n} mod n = 5, n = 1643434407157 and 5675297754009
and 12174063716147 and 162466075477787

2^{n} mod n = 7, n = 15237454403219419167053498809

2^{n} mod n = 11, n = 98828020264153 and
894157816841269897394424491194255510200782699

2^{n} mod n = 13, n = 1910102794991114096035717

2^{n} mod n = 15, n = 26598440989093

2^{n} mod n = 17, n = 3567404505159 and
106436400721299

2^{n} mod n = 19, n = 500796684074966733196301

2^{n} mod n = 23, n =
20116752226784148927290928186507

2^{n} mod n = 25, n = 3746723371601 and
840968862911681

Max Alekseyev found another solution to 2^n = 3 (mod n) using this approach in November 2006. It is 3468371109448915.

Update:I found another solution 10991007971508067 in Jan 2007 continuing with my original search back in 2000-2001.

There are infinitely more such primes. What is nice, is that for the primes that are possible divisors, you can find specific restrictions on the form of n such as:

if 5|n, n=5*(4x+3) if 19|n, n=19*(18x+13) if 23|n, n=23*(11x+8) if 29|n, n=29*(28x+5) if 47|n, n=47*(23x+19) if 53|n, n=53*(52x+17) if 71|n, n=71*(35x+16) if 97|n, n=97*(48x+19) if 101|n, n=101*(100x+69)

In general, if p|n, n=p*(hx+k) where h is the order of 2 mod p and k is a solution to 2

If needed, other analysis can further refine the list of factors for speeding up searches.

Note: The theory described here can be applied similarly to other bases besides 2.

33857 = 2^6 * 23^2 + 1 233927 = 2^3 * 3^4 * 19^2 - 1 125000 = 50^3

Here is a summary of the top results for the first 5,000,000

c |
Hits |

2 | 665328 |

8 | 240284 |

512 | 87889 |

32 | 75381 |

128 | 55180 |

2097152 | 30881 |

32768 | 28355 |

2048 | 18443 |

8192 | 15830 |

131072 | 12187 |

524288 | 7045 |

8388608 | 588 |

33857 | 90 |

233927 | 84 |

125000 | 76 |

15443 | 61 |

129032 | 58 |

48707 | 57 |

35477 | 56 |

559682 | 56 |

494018 | 55 |

2^25 = 7 (mod 25) and 2^(2^25-7) = 7 (mod 2^25-7) 2^18 = 10 (mod 18) and 2^(2^18-10) = 10 (mod 2^18-10) 2^91 = 37 (mod 91) and 2^(2^91-37) = 37 (mod 2^91-37)

This does look peculiar at first, especially with such a large value like 2

Consider the equation 2^n = c (mod n) Unless c=2, n cannot be prime so let's concern ourselves with composite n and represent n as n = x * p, where p is prime This requires (1) 2^n = c (mod x) (2) 2^n = c (mod p) And since n = x * p and 2^p = 2 (mod p) this means (3) 2^x = c (mod p) Therefore p must divide 2^x - c. If we factor 2^x - c into primes p, we have several solutions to (3). If it also happens that 2^n = c (mod x), then we have a solution to the problem. It should be obvious that with small x, you have a good chance of this happening, around 1/x. This is the factorization method of finding solutions and easily explains the patterns. If it happens for an existing solution n that 2^n - c = n * prime, you have around a 1/n chance of finding another solution. So the pattern isn't particularly helpful, except to identify the factors of 2^n - c may be useful in finding new solutions. But apparently no more useful than an arbitrary 2^x - c. Note though that the factorization approach is only capable of finding special solutions in practice (those that contain very small factors and one large prime factor). Peter Montgomery's solution to 2^n = 3 (mod n) required factoring 2^483-3. To just find the Lehmer solution, 4700063497, you would have had to factor 2^893-3. And for my 8365386194032363, factoring 2^4790708227-3.

Another interesting and open problem is to construct new solutions from given ones. I made a little progress by recognizing solutions to 2

2: Let p be the smallest prime factor of n.

3: Let d be the 'multiplicative order of 2 mod n'. That is, the smallest number such that 2^d = 1 (mod n).

4: With a solution 2^x = 1 (mod n), x is always divisible by the multiplicative order of 2 mod n.

5: With the equation 2^n = 1 (mod n), step (4) means that n must be divisible by d.

6: Since p|n, and 2^d = 1 (mod n), then 2^d = 1 (mod p). However, this means d must contain a factor from (p-1).

7: Now we have a contradiction. (2) says p is the smallest prime factor, but (5) says d|n and (6) says d has a factor from (p-1) which is smaller than p.

2^202201409 = 99 (mod 202201409) 2^4574351 = 999 (mod 4574351) 2^32743 = 9999 (mod 32743) 2^697937887 = 99999 (mod 697937887) 2^56894809 = 999999 (mod 56894809) 2^106829527 = 9999999 (mod 106829527) 2^5451050779 = 99999999 (mod 5451050779)

2^262279 = 11 (mod 262279) 2^1917403 = 111 (mod 1917403) 2^21936793 = 1111 (mod 21936793) 2^45109 = 11111 (mod 45109) 2^?????????? = 111111 (mod ??????????)[Can you find a solution?]2^8829626651 = 1111111 (mod 8829626651) 2^567989047 = 11111111 (mod 567989047)

2^1207 = 77 (mod 1207) 2^1271 = 777 (mod 1271) 2^419203 = 7777 (mod 419203) 2^141865 = 77777 (mod 141865) 2^40568093 = 777777 (mod 40568093) 2^164920309 = 7777777 (mod 164920309) 2^n = 77777777 (mod n), n=47222727390771757195151147189 or 5598655951447526819598923132276913265794639577197454266113243526525826813744462303340285

* Click here to get a database of various 2

These are all 'work in progress', so be sure to come back later to see updates!

Here are a few programs I've written to aid in your search for
solutions to b^{n}
mod n = c. They are console applications for the MS Windows
platform.

**GPL**

Efficiently finds all solutions in a given range.

**GenericPAL**

Implements the basic "Prime and Line" algorithm.

Link: http://www.immortaltheory.com/NumberTheory/GenericPAL.zip

**Gen_PowerMod_DB**

Creates a text file of solutions for a given b and c<1000. Useful if you're interested in a particular base b. You can this use program to create an initial list of solutions, then use one of the above programs on any c with no solutions.

I
used
to
host an ECM Server on this server to factor numbers of the form
2^{x}-3. See my ECM Project page for
details.
However,
that
is
no
longer
running.
Feel
free
to
use
the
programs
above
though
for
your
own
searches.

Thank you for reading my page! If you enjoyed it send me an email, I'd love to hear from you. Take care!

Joe K. Crump |