2n mod n = c

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:

` `

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.

• GPL

Efficiently finds all solutions in a given range.

• GenericPAL

Implements the basic "Prime and Line" algorithm.

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