2ⁿ mod n = c

    Since we can calculate 2ⁿ mod n relatively fast, it is natural to ask what types of numbers yield various results. We know from Fermat's Little Theorem, that 2^p mod p = 2 for primesp>2. But what kind of numbers yield a number like 3? I decided to do a search of 2ⁿ mod n results and collect those I found interesting.

    As a baseline I've searched all odd n < 1.26*10¹² for c<32. That's well over a trillion! Some of the results yielded interesting sequences which I submitted to EIS. I've also found several results not necessarily in sequence including another solution to 2ⁿ mod n = 3. On this page I'll list various solutions, describe the theory and methods used, explain some well known patterns, allow you to download my database of solutions , and campaign for you to join the search!

    Note: I may write the equation as 2ⁿ = c (mod n) but in those circumstances I'm only interested in solutions n > c. For instance, n=463 is a solution to 2ⁿ = 465 (mod n) but is not a solution to 2ⁿ mod n = 465.

First though here is my collection of the sequences which I know to be in order:

c=2n mod n	Solutions 'n' in order (e.g. gauranteed to be in sequence)
3	4700063497
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

Out of sequence results

    You can find solutions 2ⁿ mod n = c by other means rather than just iteration. For instance, you can factor 2^x-c into primes p for various x, and test N=p*x as a solution. I've found several results this way, and recently Peter Montgomery (MS Research) found another solution to 2ⁿ mod n = 3 by factoring 2⁴⁸⁵-3 with the Number Field Sieve. Another method which I only starting experimenting with recently (9/1/2000) is constructing a sieve based on restrictions described in the 'Theory' section below. This latter method, which is typically O(sqrt(n)) in performance, has turned out to be very effective and on 9/18/2000 I found yet another solution to 2ⁿ mod n = 3 with it! Here are some solutions found so far by these methods...

    2ⁿ mod n = 3, n = 8365386194032363
    2ⁿ mod n = 3, n = 63130707451134435989380140059866138830623361447484274774099906755
    2ⁿ mod n = 5, n = 1643434407157 and 5675297754009 and 12174063716147 and 162466075477787
    2ⁿ mod n = 7, n = 15237454403219419167053498809
    2ⁿ mod n = 11, n = 98828020264153 and 894157816841269897394424491194255510200782699
    2ⁿ mod n = 13, n = 1910102794991114096035717
    2ⁿ mod n = 15, n = 26598440989093
    2ⁿ mod n = 17, n = 3567404505159 and 106436400721299
    2ⁿ mod n = 19, n = 500796684074966733196301
    2ⁿ mod n = 23, n = 20116752226784148927290928186507
    2ⁿ 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.

Some Theory

    For a given 'c', you can find a lot of restrictions on 'n' using elementary number theory. For example, consider 2ⁿ = 3 (mod n). If a solution 'n' was divisible by 3, this would mean 2^3x = 3 (mod 3x) requiring 2^3x = 3 (mod 3). This simplifies to 2^x = 0 (mod 3) which is impossible so 3 can never divide n. Similarly all of the following primes also cannot divide n:

---

3, 7, 11, 13, 17, 31, 37, 41, 43, 59, 61, 67, 73, 79, 83, 89, 103, 107, 109, 113, 127, 131, 137

---

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 the least solution to 2^k mod p = c. If k doesn't exist then p cannot divide n. Sometimes a k exist, but GCD(h,k) contains another prime that cannot divide n, thus p cannot divide n. By iteratively choosing p and constructing n=p*(hx+k), you can drastically reduce the number of calculations needed to find the next solution. I call this the "prime and line" method because you are combining a given prime with numbers chosen from the line hx+k. This style of iterating also has the benefit of eliminating all prime n by virtue of constructing n in factored form.

---

Distribution

    Let's consider what type of result we should expect when computing 2ⁿ mod n. For the sake of this page's interest, I'll only consider odd n. First, it should be obvious that 2ⁿ mod n is mostly even. The single most common result is 2 where n is prime. Next up, are odd powers of 2 which makes sense considering the equation and using odd n. However, after that I was surprised to find odd numbers that, for no apparent reason, occurred very often! The first you'll find is 33857. It occurs a whopping 90 times using the first 5,000,000 odd numbers, second only to odd powers of 2. Next up was 233927 which occurred 84 times, followed by the interesting 125000 which occurred 76 times. At first 33857 dominated these three, but 233927 quickly caught up suggesting another number below it would quickly catch up to these, etc. Certain representations of some of these look suspicious:

---

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

---

    One reason why 33857 occurs so often is most likely related to the number of possible small prime divisors. For instance using elimination tactics as described earlier doesn't eliminate many small primes. It has possible solution divisors {3,5,11,13,19,29,37,41,47,59,61,79,83,...}, where most 'c' do not have as many and thus have less chance of a given n being a solution.
 Here is a summary of the top results for the first 5,000,000 odd numbers:

---

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

---

Patterns

    Maybe someday we'll have a method or formula for iterating the various values of n satisfying 2ⁿ mod n = c. Examining the growth of the results and the nature of the equation itself you shouldn't expect any sort of simple polynomial or exponential formulas for all solutions. However there may be a simple formula that will help us find 'some' solutions for particular equations. I along with many others noticed the following which looked like some kind of pattern...

---

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⁹¹-37 satisfying an equation. However, it can be explained quite easily looking at the factoring method in more detail.

---

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ⁿ = c (mod n) can often be used to create solutions to 2ⁿ = c^p (mod n).  If 2^m = c (mod m) and 2^m = c (mod p) and p odd, then 2^mp = c^p (mod mp). In the equation 2ⁿ = 3 (mod n), there are known solutions that satisfy 2ⁿ = 3 (mod 5).  By the above these generate solutions to 2ⁿ = 3⁵ = 243 (mod n). So now we have some cool solutions to 2ⁿ = 243 (mod n), such as n=41826930970161815 and n=315653537255672179946900700299330694153116807237421373870499533775. Other than this however, not much progress has been made. If a reliable way were found to construct a new solution to the same equation you would also have a proof that infinite solutions exist. That would be very rewarding!  No proof exists yet showing there are infinite solutions for c>1.      Some folks have asked me about the proof there is no solution 2ⁿ mod n = 1. It's not difficult to prove. Here's a rough-draft I put together although I'm not the first to use this logic:

-------------------------------

1: Proof by contradiction: Let's assume some n exists such that 2^n = 1 (mod n)

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.

Having fun...

    Here are some other results. Some are admittedly not too interesting but at least entertaining (which is what number theory is all about for me)! :)

---

   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

---

My database(s)

    * Click here to get the '2ⁿ mod n = c' database.
    * Click here to get a database of various 2^x-3 factorizations.

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

---

Join the search!!!

I setup an ECM Server on this server to factor numbers of the form 2^x-3. See my ECM Project page for details if you would like to help out.