2n mod n = c

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

 

    Originally, I searched all odd n < 1.26*1012 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 2n 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 2n = c (mod n) but in those circumstances I'm only interested in solutions n > c. For instance, n=463 is a solution to 2n = 465 (mod n) but is not a solution to 2n mod n = 465.

First here is a small example of sequences which are known to be in order:

c=2n 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

Out of sequence results

 

    You can find solutions 2n mod n = c by other means rather than just iteration. For instance, you can factor 2x-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 2n mod n = 3 by factoring 2485-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 2n mod n = 3 with it! Here are some solutions found so far by these methods...

    2n mod n = 3, n = 8365386194032363
    2n mod n = 3, n = 63130707451134435989380140059866138830623361447484274774099906755
    2n mod n = 5, n = 1643434407157 and 5675297754009 and 12174063716147 and 162466075477787
    2n mod n = 7, n = 15237454403219419167053498809
    2n mod n = 11, n = 98828020264153 and 894157816841269897394424491194255510200782699
    2n mod n = 13, n = 1910102794991114096035717
    2n mod n = 15, n = 26598440989093
    2n mod n = 17, n = 3567404505159 and 106436400721299
    2n mod n = 19, n = 500796684074966733196301
    2n mod n = 23, n = 20116752226784148927290928186507
    2n 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 2n = 3 (mod n). If a solution 'n' was divisible by 3, this would mean 23x = 3 (mod 3x) requiring 23x = 3 (mod 3). This simplifies to 2x = 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 a solution to 2k 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.

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 2n mod n. For the sake of this page's interest, I'll only consider odd n. First, it should be obvious that 2n 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 2n 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 291-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 2n = c (mod n) can often be used to create solutions to 2n = cp (mod n).  If 2m = c (mod m) and 2m = c (mod p) and p odd, then 2mp = cp (mod mp). In the equation 2n = 3 (mod n), there are known solutions that satisfy 2n = 3 (mod 5).  By the above these generate solutions to 2n = 35 = 243 (mod n). So now we have some cool solutions to 2n = 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 2n 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

Databases

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

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


Programs

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

Efficiently finds all solutions in a given range.

Link: http://www.immortaltheory.com/gpl.zip

Implements the basic "Prime and Line" algorithm.

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

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.

Link: http://www.immortaltheory.com/gen_powmod_db.zip


Join the search!!!

I used to host an ECM Server on this server to factor numbers of the form 2x-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 | Number Theory Home