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 primes p>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.

    Originally, I 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 , offer some programs, 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 here is a small example of sequences which are known to be in order:

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:

        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)

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. 

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:

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)

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.

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

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

Databases

    * 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!

Programs

Join the search!!!

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.